1. ## sorting a linked list using merge sort question..

i thought of breaking it into two lists merge them and sorting them
in this way
Code:
```node* merge(node* l1,node* l2)
{
if ((!l1)&&(!l2))
{
return NULL;
}
if (!l1)
{
v1=99999999999;
v2=l2->val;
}
if (!l2)
{
v2=99999999999;
v1=l1->val;
}
if (v1>v2)
{
l2->next=merge(l1,l2->next);
return l2;
}
else
{
l1->next=merge(l1->next,l2);
return l1;
}
}```
but i dont have this breaking into two stuff here??

because i need to sort a single linked list
??

2. Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.

Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.
i'll do both.
first my original question:
i got an idea to use a spliting function
i split it in half and send it to merge.
Code:
```    node* split(node* l)
{
node* l1,*l2,*t,*r;
l=t=r;
if (!l) return NULL;
if(!l->next) return l;
while(r)//turtle rabbit algorithm
{
r=r->next;
prev=t;
t=t->next;
if (t->next)
{
r=r->next;
}
prev->next=NULL;
return merge(l,t);
}```
its not a real mergesort because i split it only ones
??(is it ok??)

regarding sorting by selection sort :
i only can sort it by value.(fliiping the values)
there is no way i could think of so many relinking to do
in a recursive way.(like i did before)

4. Is it OK to split a mergesort just once? No. Mergesort relies on each sub-string being sorted before the two are merged together. It could happen with just a single split, but it's *extremely* unlikely.

You don't have to re-link all the nodes as you sort, just swap the values which the nodes contain. That's fine! You can swap a whole struct very easily, with all it's members, if you need to. You don't have to swap each member of the struct, individually.

An alternative would be to use mergesort on the larger substrings, and use selection sort, on only the smaller substrings, after you've made a split or two (or four or whatever), and then merge the substrings back together again.

Do you *have* to use a mergesort as one of your linked list sorting algorithms?

5. but look at my merge function
it doesnt need a sorted lists
its merging two unsorted lists
into a sorted one

6. ahh you are correct

Code:
``` node* split(node* l)
{
node* l1,*l2,*t,*r;
l=t=r;
if (!l) return NULL;
if(!l->next) return l;
while(r)//turtle rabbit algorithm
{
r=r->next;
prev=t;
t=t->next;
if (t->next)
{
r=r->next;
}
prev->next=NULL;
return merge(split(l),split(t));
}```

7. Originally Posted by kakaroto
but look at my merge function
it doesnt need a sorted lists
its merging two unsorted lists
into a sorted one
I've heard of the turtle & rabbit algorithm, but have not used it or studied it. I don't have any opinion of it, pro or con, nor do I know if you have implemented it properly.

There are more ways to sort data than you might imagine. If you want a recommendation for sorting a linked list, I recommend selection sort. If you have another algorithm that works, and you like it's performance, then sure, use it.

8. ok thanks

9. Ok. I have a question, which is related to sorting a linked list, and that's why I didn't create any thread for it. I just want to sort a singly linked list, should I also go for selection sort(I'm assuming heap sort), as Adak posted in his earlier post in this thread. I want the code to be most efficient.

10. Insertion, bubble, and selection sort are all very fast if the number of items to be sorted is less than 25 or so. Even in arrays, they're quicker than standard Quicksort (and frequently used as an enhancement to Quicksort, on the smaller sub arrays it generates).

After 25, I would look at Cocktail and Comb 11 algorithms, because they're basically bi-directional versions of one (sometimes two), of the above sorting algorithms. I've only tested the Comb 11 version on arrays, but it is *very* good on large quantities of data - within a hair of equaling Quicksort. I'm not a big fan of Heapsort, but it can also be quite fast.

You will need to do some testing on linked list sorting, to see what works best with your specific data.

You will need to do some testing on linked list sorting, to see what works best with your specific data.
How? I mean by calculating the Big O thing or something else.

Use selection sort instead, you'll be 100% happier, guaranteed. Merge sort is fine, but stinks on a linked list.
This is completely false. I've done comparative performance testing with sorts on a linked list (bubble, insertion, selection, merge and quick), and merge sort has all the advantages over selection sort, etc that it does on an array. Which is to say, on a very large linked list, it and quicksort perform exponentially better than anything else, including selection sort. That is, they will do in seconds what takes minutes for selection sort.

13. Originally Posted by MK27
Which is to say, on a very large linked list, it and quicksort perform exponentially better than anything else, including selection sort.
Agreed, plus merge sort on a linked list does not need the extra space consumption as does merge sort on an array.

14. Originally Posted by laserlight
Agreed, plus merge sort on a linked list does not need the extra space consumption as does merge sort on an array.
Yep, because you just swap pointers. I just tried this again to demonstrate:

Command (h for help, Q to quit): N
How many records? 25000
New list is 3515.62 kb

Command (h for help, Q to quit): s

Selectionsorting....
624950002 Iterations Comparison calls: 312487500
Elapsed time: 2 min 10 sec

Command (h for help, Q to quit): S
Shuffled.

Command (h for help, Q to quit): m

Mergesorting..............24999 function calls
503757 Iterations Comparison calls: 334111
Elapsed time: 0 min 0 sec

The bigger the list, the more severe the difference. Merge sort will still do 100's of thousands in several seconds, while selection sort is simply not worth waiting for at that point.

If anyone wants to look at the implementation I used for that: