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:
unsigned_cmp(a, b)
true for all pairs of nodes where a is before b.
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.