To sort a doubly-linked list: sort, then traverse the forward links to regenerate the reverse links.
Written by Jamie Lokier 1995-1999. Version 2.0.
Properties ==========
1. Takes O(n) time to sort a nearly-sorted list; very fast indeed.
2. Takes O(n log n) time for worst case and for random-order average. Worst case is a reversed list. Sorting is still fast. NB: This is much faster than unmodified quicksort, which is O(n^2).
3. Requires no extra memory: sorts in place like heapsort and quicksort. Uses a small array (typically 32 pointers) on the stack.
4. Stable: equal elements are kept in the same relative order.
5. Macro so the comparisons and structure modifications are in line. You typically have a C function which calls the macro and does very little else. The sorting code is not small enough to be worth inlining in its caller; however, the comparisons and strucure modifications generally _are_ worth inlining into the sorting code.
Requirements ============
Any singly-linked list structure. You provide the structure type, and the name of the structure member to reach the next element, and the address of the first element. The last element is identified by having a null next pointer.
How to sort a list ==================
Call as `FAST_MERGE_SORT (LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'.
`LIST' points to the first node in the list, or can be null. Afterwards it is updated to point to the beginning of the sorted list.
`TYPE' is the type of each node in the linked list.
`NEXT' is the name of the structure member containing the links. In C++, this can be a call to a member function which returns a non-const reference.
`LESS_THAN_OR_EQUAL_P' is the name of a predicate which, given two pointers to objects of type `TYPE', determines if the first is less than or equal to the second. The equality test is important to keep the sort stable (see earlier).
The total number of items must fit in `unsigned long'.
How to update a sorted list ===========================
A call is provided to sort a list, and combine that with another which is already sorted. This is useful when you've sorted a list, but later want to add some new elements. The code is optimised by assuming that the already sorted list is likely to be the larger.
The already sorted list comes earlier in the input, for the purpose of stable sorting. That is, if an element in the already sorted list compares equal to one in the list to sort, the element from the already sorted list will come first in the output.
Call as `FAST_MERGE_SORT_APPEND (ALREADY_SORTED, LIST, TYPE, NEXT, LESS_THAN_OR_EQUAL_P)'.
`ALREADY_SORTED' points to the first node of an already sorted list, or can be null. If the list isn't sorted already, the result is undefined.
`LIST' points to the first node in the list to be sorted, or can be null. Afterwards it is updated to point to the beginning of the combined, sorted list.
Algorithm =========
It identifies non-strictly ascending runs (those where Elt(n) <= Elt(n+1)), and combines ascending runs in a hybrid of bottom-up and non-recursive, top-down mergesort.
Robert Sedgewick, ``Algorithms in C'', says that merging runs incurs more overhead in practice than it saves, because of the extra processing to identify the runs, except when the list is very nearly sorted. He says that is because the extra processing occurs in the inner loop, which suggests that he means to repeatedly identify pairs of runs and merge them, in a bottom-up process. (That is consistent with the adjacent text). The implementation here only identifies the runs once, so Robert's argument doesn't apply.
Five optimisations are implemented:
1. Runs of ascending elements are identified just once.
2. A stack of runs is maintained. This is analogous to the explicit stack used in a non-recursive, top-down implementation. However, the pure top-down algorithm could not identify runs of ascending elements once, without requiring additional storage for the runs' head nodes.
3. A top-down implementation must divide each list into two smaller lists. This implementation does not do that.
4. A decision tree is used to sort up to three elements per run, so the initial runs are all at least three elements long (except at the end of the list).
5. Unnecessary memory writes are avoided by using two loops for merging. Each loop identifies contiguous elements from one input list. This also biases the code path to the contiguous cases.
As well as being fast, identifying ascending runs allows the sort to be "stable", meaning that objects that compare equal are kept in the same relative order.
With some extra complexity, and overhead, it is possible to identify alternating ascending and descending runs. That is not implemented here because it wouldn't be useful for most applications.
Notes =====
This loop forces initial runs to be at least 3 elements long, if there are enough elements. I haven't properly tested if the extra code for this is worthwhile. It seems to win most times, but not all. It may be that even the code to force 2 element runs is unnecessary. In one case, forcing at least 2 elements was about 5% worse than forcing at least 3 elements _or_ accepting 1 element; the latter two cases had very similar numbers of comparisons.
Need to count (a) time; (b) comparisons.
An earlier version of this thing was measured on serious real time code, and was pretty fast.
Go to the source code of this file.
Defines | |
| #define | __FAST_MERGE_SORT |
| #define | __FAST_MERGE_SORT_LABEL(name) __FAST_MERGE_SORT_LABEL2 (name,__LINE__) |
| #define | __FAST_MERGE_SORT_LABEL2(name, line) __FAST_MERGE_SORT_LABEL3 (name,line) |
| #define | __FAST_MERGE_SORT_LABEL3(name, line) __FAST_MERGE_SORT_/**/name/**/_/**/line |
| #define | FAST_MERGE_SORT(__LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P) __FAST_MERGE_SORT(1, 0, __LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P) |
| #define | FAST_MERGE_SORT_APPEND(__ALREADY_SORTED, __LIST,__TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Value: __FAST_MERGE_SORT(0, __ALREADY_SORTED, __LIST, \ __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P) |