# Thread: Quick Sort or Merge Sort???

1. ## 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!

2. >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.

3. HERE IS THE CONCEPT THAT I WAS LOOKING AT
Code:
```struct bucket_struct{
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.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.tail->nxt = l1
l1 = l1->nxt
}
else
if(newList = NULL)
{
}
newList.tail->nxt = l2
l2 = l2->nxt
}
}
I DUNNO THOUGH?

4. 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.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)
{
{
}
newList.tail->nxt = l1;
l1 = l1->nxt;
}
else
{
{
}
newList.tail->nxt = l2;
l2 = l2->nxt;
}
}
}

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

5. 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;
}```

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

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