🚀 go-pugleaf

In article <martelli.813833367@cadlab>,
martelli@cadlab.cadlab.it (Alex Martelli) wrote:

>>What do you do if you need a stable sorter?  Or what does Num Rec.
suggest for
>
>You take the index into account in your comparison function, as a
>"secondary key", if the items being sorted are otherwise equal.
...
>int stablecompare(void *a, void *b)
>{
>    if(int comparison=gencompare(a,b)) return comparison;
>    return (a<b)?-1:(a>b)?1:0;
>}

This does not work with most partitioned sorts, except merge sort
(which requires additional storage).  Consider the array [10, 5a, 5b,
6].  Here I use the notation 5a and 5b to designate two records with
the same key (5).

Let's assume that the sort routine effectively sorts this by sorting
the odd entries, the even entries, and then doing a bubble sort
(don't laugh -- this is effectively the last stage of a Shell sort).

Original array                  [10, 5a, 5b, 6].
First we sort [10, 5b] yielding [5b, 5a, 10, 6].
Next sort     [5a, 6]  getting  [5b, 5a, 10, 6].
Last pass                       [5b, 5a, 6, 10].

Notice that when we sorted the subsets, the relative positions of the
5's got changed, so that when they got compared in the final pass, the
did not get restored to stable order.

Thad