Re: three-way comparison Aubrey Jaffer 02 Nov 2006 21:24 UTC
| 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.