Computer science literature is packed full of sorting algorithms, and all of them seem to operate on arrays. Everybody knows the Sorting Facts Of Life:
O(N log
N) limit;
O(N) auxiliary
space;
Nobody tells you what to do if you want to sort something other than an array. Binary trees and their ilk are all ready-sorted, but what about linked lists?
It turns out that Mergesort works even better on linked lists than
it does on arrays. It avoids the need for the auxiliary space, and
becomes a simple, reliably O(N log N) sorting
algorithm. And as an added bonus, it's stable too.
Mergesort takes the input list and treats it as a collection of
small sorted lists. It makes log N passes along the
list, and in each pass it combines each adjacent pair of small
sorted lists into one larger sorted list. When a pass only needs to
do this once, the whole output list must be sorted.
So here's the algorithm. In each pass, we are merging lists of size
K into lists of size 2K. (Initially
K equals 1.) So we start by pointing a temporary
pointer p at the head of the list, and also preparing
an empty list L which we will add elements to the end
of as we finish dealing with them. Then:
p is null, terminate this pass.
K lists, so increment the number of merges
performed in this pass.
q, at the same place
as p. Step q along the list by
K places, or until the end of the list, whichever comes
first. Let psize be the number of elements you managed
to step q past.
qsize equal K. Now we need to merge a
list starting at p, of length psize, with
a list starting at q of length at most
qsize.
psize > 0) or the q-list is
non-empty (qsize > 0 and
q points to something non-null):
e, from the start of its list, by
advancing p or q to the next element
along, and decrementing psize or qsize.
e to the end of the list L we are
building up.
p until it is where q
started out, and we have advanced q until it is
pointing at the next pair of length-K lists to merge.
So set p to the value of q, and go back to
the start of this loop.
As soon as a pass like this is performed and only needs to do one
merge, the algorithm terminates, and the output list L
is sorted. Otherwise, double the value of K, and go
back to the beginning.
This procedure only uses forward links, so it doesn't need a doubly
linked list. If it does have to deal with a doubly linked
list, the only place this matters is when adding another item to
L.
Dealing with a circularly linked list is also possible. You just
have to be careful when stepping along the list. To deal with the
ambiguity between p==head meaning you've just stepped
off the end of the list, and p==head meaning you've
only just started, I usually use an alternative form of the "step"
operation: first step p to its successor element, and
then reset it to null if that step made it become equal to the head
of the list.
(You can quickly de-circularise a linked list by finding the second element, and then breaking the link to it from the first, but this moves the whole list round by one before the sorting process. This wouldn't matter - we are about to sort the list, after all - except that it makes the sort unstable.)
Like any self-respecting sort algorithm, this has running time
O(N log N). Because this is Mergesort, the worst-case
running time is still O(N log N); there are no
pathological cases.
Auxiliary storage requirement is small and constant (i.e. a few
variables within the sorting routine). Thanks to the inherently
different behaviour of linked lists from arrays, this Mergesort
implementation avoids the O(N) auxiliary storage cost
normally associated with the algorithm.
Any situation where you need to sort a linked list.
Sample code in C is provided here.