
	SORTING

In List_SortOnKey, the list is used as follows:

The list is split into a set of single-linked sub-lists by walking
the original list and finding sorted sub-sequences ("chains").  The
chaines are hung off the pPrev node, linking through pPrev.

The length of the chains are assured to be at least two by
handling any final 'stray' entries separately (merging them into
the first list - merging them into the last list would create a bad
case, as they have already been rejected for fitting head/tail of
that list).


Due to the guaranteed length, the 2nd node of each chain has its
pNext used to store a pointer to the last entry in the chain.  Ie,
if you have the head of a chain, you can get the tail as
node->pPrev->pNext.  This is used to merge two non-overlapping
lists without having to traverse one of them.

		Advanced alternatives:

There are more advanced datastructures that might be better for some
cases.  I've included a description of two of them.

    "Length and last"

This datastructure store the length of each list, thus allow
heuristics over which list should be merged.

For the initial splitting, each time a list end up being two
entries long it is placed on a special list of sub-lists for
sub-lists that are two entries long.

Given this, we now have space for two pieces of information
attached to each list: The length of the list, and the tail node of
the list.  This information is stored in the next-pointers of the
second and third entries in the list (the first next-pointer being
used to store the list-of-lists).

This gives this layout of this form:
 n1 ------> n5 ------> n2
  |          |          |
  V          V          V
 n3->len    n7->len    n4->len
  |          |          |
  V          V          V
n18->last  n14->last   n6->last
             |
             V
           n19

Downwards arrows are node->pPrev, rightwards arrows are
node->pNext.  Now, notice how the free parts of each node is used
as a structure, and the minimum length of a chain is exploited.
Filling in the real values for the above example, we get

 n1 ------> n5 ------> n2
  |          |          |
  V          V          V
 n3-> 3     n7-> 4     n4-> 3
  |          |          |
  V          V          V
n18->&n18  n14->&n19   n6->&n6
             |
             V
           n19

    "Fully linked"

