Best way to sort a linked list?

[stingBlah]

I know the common algorithms to sort arrays (Insertion, ShellSort, HeapSort, MergeSort, QuickSort), but what is the best way to sort a singly linked list?

What if we are optimizing for space?

Ignoring space requirements, is it possible to achieve this in O(N) time?

Thanks!

[helios]

There are no general algorithms to sort anything, lists or otherwise, in O(n). There are some specialized algorithms that can, but they're generally not very good.

Quick sort could be implemented for lists. Although if you have data that needs to be sorted, a list are not the best choice.

[stingBlah]

So Quicksort would be the best way?

I read that Insertion sort actually works much more efficiently for lists than for arrays...

[helios]

Insertion sort has an average time of O(n²). Quick sort has an average time of O(n log n). If the list is doubly linked, it's possible to implement quick sort so that it's even faster than with arrays by choosing the first or the last nodes (possibly at random) as pivots and by taking advantage of the list's fast swap time.

EDIT: But choosing the first or last node as the pivot for a quick sort can give very bad results if the set is almost sorted. Depending on the application and size of the list, it may be preferable to move to a random node at each recursive call.

[stingBlah]

I was actually curious about the answer to an MS interview question:

Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.

But I guess this one doesn't really have a possible answer...

[jsmith]

I suppose it depends upon what N is referring to.

Typically the runtime efficiency "Big-O" of sorting algorithms is defined in terms of the number
of comparisons required, as a function of the number of elements in the list (N).

But with singly linked lists, arguably a better metric would be number of pointer chases
required since linked lists are by nature not random access.

EDIT: It occurs to me that looking at the implementation of std::list<>::sort() would be a
good starting point. I'm sure the algorithm chosen there is probably the "best" one.

[1yR4jE8b]

If it's a singly linked list, a Selection sort would probably be the easiest to implement.

[n4nature]

If N is a small number, Insertion sort is the fastest, even though its run time is O(N^2). Its an inplace sorting algo, since you're optimizing for space. Even heapsort is an inplace algo, with runtime O(nlogn), with best worst-case running time. Quicksort is O(nlogn), but not sure if its ideal for a singly linked list. Same with mergesort.

There is no way to sort it in O(N), ofcourse considering a big and random N

[Chriscm]

That's not entirely accurate. O(N) sorting is possible using a radix sort. A radix sort is great on data where you know the size of the key will be smaller than logN. A radix sort, worst case, takes KeySize, passes through data to sort your data. As such size of the key considered your total run time is O(N*K) where N is the size of your data and K is the length of your key. Something to watch out for though is cases where your key is very long and your data isn't. As stated above the best possible sorting algorithms based on comparisons of keys is O(NlogN), not that log in this case is log_base2, this isn't usually important, however in this case we need to do some math to know when a radix sort is a bad idea. And this is precisely when logN < KeySize.

Another thing to note on some of the above comments is whether or not your list structure supports direct access or not. If your list is a true "linked list" as in you need to access elements in order, I would recomend a 2 fold approach. On the first pass through your list start your traditional radix sort. If on this pass you determine that your data size is less than 2^keysize, sort your sublists using one of the known sorting algorithms, I find heapsort best if you don't feel like optimizing, however a well optimized quicksort is on average the best of the O(NlogN) algorithms.

However, if it is required that throughout you maintain your Linked list data structure, I believe an insertion sort is probably your best option. Hope that helps!

[luisespinal]

>>> I read that Insertion sort actually works much more efficiently for lists than for arrays.

And where did you read that????