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;
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
K equals 1.) So we start by pointing a temporary
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:
pis null, terminate this pass.
Klists, so increment the number of merges performed in this pass.
q, at the same place as
qalong the list by
Kplaces, or until the end of the list, whichever comes first. Let
psizebe the number of elements you managed to step
K. Now we need to merge a list starting at
p, of length
psize, with a list starting at
qof length at most
psize > 0) or the q-list is non-empty (
qsize > 0and
qpoints to something non-null):
e, from the start of its list, by advancing
qto the next element along, and decrementing
eto the end of the list
Lwe are building up.
puntil it is where
qstarted out, and we have advanced
quntil it is pointing at the next pair of length-
Klists to merge. So set
pto 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
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
Dealing with a circularly linked list is also possible. You just
have to be careful when stepping along the list. To deal with the
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
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.
(back to algorithms index)