# Quick Sort or Merge Sort???

• 11-10-2005
swanley007
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!
• 11-10-2005
Prelude
>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.
• 11-10-2005
swanley007
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?
• 11-10-2005
swanley007
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) { }```
• 11-10-2005
swanley007
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;                  }```
• 11-10-2005
swanley007
Before the while I added stepper = start; in the find mid......Now an infinate loop in the merge sort
• 11-10-2005
swanley007
I found that the loop is because of the terminating case in the mergesort function....I don't know what to use!