mergesortlinkedlist() is a function to sort a singly linked list. Most sorting routines assume random access to the items to be sorted. Two typical examples are the standard Unix qsort(3) function, and the C++ STL sort function. However, there is a long tradition of sorting data to which only sequential access is possible. This dates from the days in which large quantities of data were stored on tape. Algorithms for sorting data on tape are suitable for use on linear linked lists, and one known to be good is mergesort. It takes O(N log N) time for N inputs, both average and worst-case.

The example given here works in two phases. In phase 1, the input list is divided between lists a and b by putting alternating runs onto each list. In phase 2, it merges runs from lists a and b, appending the merged runs alternately onto c and d. At the end of each pass in phase 2 lists a and b are reloaded from c and d. The algorithm terminates when it finds that there is only one run left (i.e. that list b is empty when attempting to start another pass of phase 2).


The mergesortlinkedlist function is run like this:

	newroot = mergesortlinkedlist(oldroot, unsigned_cmp);

where the items required are:

A pointer to the first item on the list.
The comparison function to use. The resuling list will have
	unsigned_cmp(a, b)

true for all pairs of nodes where a is before b.

A pointer to the first item of the sorted list.

The source code

The source for mergesortlinkedlist is available at mergesortlinkedlist.c. It is licenced for use in accordance with the terms of the GNU General Public Licence.