Re: threeway comparison Aubrey Jaffer (02 Nov 2006 21:24 UTC)
Re: threeway comparison Aubrey Jaffer 02 Nov 2006 21:24 UTC
 From: xxxxxx@FernUniHagen.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 SRFI32) we will see such a beast :)

 Threevalued 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 SRFI95 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 3way branching offers no improvement in mergesort; and there is
little reason to use a sorting algorithm with poorer performance.
 A threevalued comparison function also speeds up other algorithms,
 e.g. vectorbinarysearch.
It is also good for sequence comparison.