Mergesort For Linked Lists

Introduction

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:

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.

Algorithm Description

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:

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

Complexity

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.

Applications

Any situation where you need to sort a linked list.

Sample Code

Sample code in C is provided here.

(back to algorithms index)


(comments to anakin@pobox.com)
(thanks to chiark for hosting this page)
(last modified on Sat Dec 11 09:44:22 2004)