| From: xxxxxx@FernUni-Hagen.de
 | Date: Mon, 23 Oct 2006 10:36:56 +0200 (CEST)
 |
 | Hello.
 |
 | Thanks Aubrey for drafting a sorting SRFI. Maybe this time (after
 | the withdrawn SRFI-32) we will see such a beast :-)
 |
 | Three-valued comparison function are more efficient for some data
 | types if many duplicates are present.  I often sort lists of some
 | million strings of average length 20 and many duplicates. I
 | remember that some sort algorithms will test (< a b) and (< b a) in
 | certain constellations for one setting of a and b.

But SRFI-95 mandates stable sort algorithms.  I traced the predicate
while (merge-) sorting various lists.

  (sort '(7 6 9 5 4) (lambda (x y) (< (quotient x 4) (quotient y 4))))
  (sort '(7 6 9 5 4) (lambda (x y) (<= (quotient x 4) (quotient y 4))))

There were no extra reversed comparisons.

So 3-way branching offers no improvement in merge-sort; and there is
little reason to use a sorting algorithm with poorer performance.

 | A three-valued comparison function also speeds up other algorithms,
 | e.g. vector-binary-search.

It is also good for sequence comparison.