Quick Sort or Merge Sort???

Hello,

I have a college assignment due TONIGHT!!!!!!! I am having a lot of trouble.... I have been trying by hand on paper and in DevC++ and with pictures...I am very frustrated to say the least. My assignment is to do a mergesort or a Quicksort on a linked list.

The list is singaly linked and I have to write all of the code for the list...can't ust the ADT's of STL's for list the others like strcmp, etc are ok. I have no ideas left. If there is a willing programmer out there that could help it would be great. I have some code, but I think that itis so garbled that I am not going to post it.

ALSO I have used these boards before with only about a 10% success rate. Please only help if you are willing to see it through until the end...I am have a problem with getting help from people who guide me into a corner and then simply stop posting.

To anyone that will help...Thank you already!

>I have a college assignment due TONIGHT!!!!!!!
Uh huh. That's a common issue.

>My assignment is to do a mergesort or a Quicksort on a linked list.
Well, merge sort is well suited to linked lists, so that's not much of a problem. Following that link will give you one hell of a head start. Since you said merge sort or quicksort, I'd suggest you go with merge sort because quicksort takes some thought (even though it's a terribly interesting exercise) while merge sort is pretty self-explanatory for lists. You don't sound like you're looking for a terribly interesting exercise at the moment.

HERE IS THE CONCEPT THAT I WAS LOOKING AT

Code:

---

struct bucket_struct{
      node* head;
      node* tail;
};


mergesort (start,stop)
    if (start->nxt != NULL)
    {
          mid = findmid(start,stop);
          mergesort(start,mid)
          mergesort(mid->nxt,stop)
          merge(start,mid,stop)
    }


merge(start,mid,stop)
bucket_struct newList;
newList.head=NULL
newList.tail=NULL
node *l1 = start
node* l2 = mid->nxt;
mid->nxt = NULL;

while(l1 != NULL && l2 != NULL)
{
    if(l1->field <= l2->field)
    {
        if(newList = NULL)
        {
            newList.head = l1
        }
        newList.tail->nxt = l1
        l1 = l1->nxt
    }
    else
        if(newList = NULL)
        {
            newList.head = l2
        }
        newList.tail->nxt = l2
        l2 = l2->nxt
      }
}
start_ptr = newList.head

---

I DUNNO THOUGH?

Here is my compiling code thus far

Code:

---

void mergesort(node *start,node *stop)
{
    node * mid;
    if (start->nxt != NULL)
    {
          mid = find_mid(start,stop);
          mergesort(start,mid);
          mergesort(mid->nxt,stop);
          merge(start,mid,stop);
    }

}
void merge(node *start,node *mid,node *stop)
{
bucket_struct newList;
newList.head=NULL;
newList.tail=NULL;
node *l1 = start;
node* l2 = mid->nxt;
mid->nxt = NULL;

while(l1 != NULL && l2 != NULL)
{
    if(l1->node_struct.d_name <= l2->node_struct.d_name)
    {
        if(newList.head= NULL)
        {
            newList.head = l1;
        }
        newList.tail->nxt = l1;
        l1 = l1->nxt;
    }
    else
    {
        if(newList.head = NULL)
        {
            newList.head = l2;
        }
        newList.tail->nxt = l2;
        l2 = l2->nxt;
      }
}
start_ptr = newList.head;
}

node *find_mid(node *start, node *stop)
{
}

---

Here is my updated find_mid function

Code:

---

node *find_mid(node *start, node *stop)
{
    int i = 0;
    node * stepper;
    int j;
   
    while(stepper != stop)
    {
                  stepper = stepper->nxt;
                  i++;
    }
    stepper = start;
    for(j = i; j > 0; j--)
    {
          stepper = stepper->nxt;
    }
    return stepper;                 
}

---

Before the while I added stepper = start; in the find mid......Now an infinate loop in the merge sort

I found that the loop is because of the terminating case in the mergesort function....I don't know what to use!