## Ternary sorting

**T**he last Le Monde puzzle made me wonder about the ternary version of the sorting algorithms, which all seem to be binary (*compare x and y, then*…). The problem is, *given (only) a blackbox procedure that returns the relative order of three arbitrary numbers, how many steps are necessary to sort a series of n nnumbers?* The heapsort entry in Wikipedia mentions a ternary sorting version, but does not get into details. Robert Sedgewick (author of a fabulous book on algorithmic I enjoyed very much when I started programming) has a talk about the optimality of *quicksort* where he mentions ternary sorting, but this seems to be more related with ties than with my problem… It is of course highly formal in that I do not know of a physical device that would justify moving from binary to ternary comparisons.

April 30, 2012 at 12:12 am

[…] is not particularly surprising: computing a median takes longer than computing a mean, even using quicksort!, hence computing two medians… Still, having to wait about six times longer for the delivery […]