Ternary sorting

The 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.

Le Monde puzzle [#28]

The puzzle of last weekend in Le Monde was about finding the absolute rank of x₉ when given the relative ranks of x₁,….,x₈ and the possibility to ask for relative ranks of three numbers at a time. In R terms, this means being able to use

> rank(x[-9])
[1] 1 7 4 6 8 3 2 5
> rank(x[1:3])
[1] 1 3 2

or yet being able to sort the first 8 components of x

> x[-9]=sort(x[-9])
> rank(x[c(1,8,9)])
[1] 1 3 2

and then use rank() over triplets to position x₉ in the list. If x₉ is an extreme value, calling for its rank relative to x₁ and x₈  is sufficient to find its position. Else repeating with the rank relative to x₂ and x₇, then relative to x₃ and x₆  , etc., produces the absolute rank of x₉ in at most 4 steps. However, if we first get the rank relative to x₁ and x₈,  then the rank relative to x₄ and x₅, we only need at most an extra step to find the absolute rank of x₉ in thus at most 3 steps. Yet however, if we start with the rank relative to x₃ and x₆, we are left with a single rank call to determine the absolute rank of x₉ since, whatever the position of x₉ relative to x₃ and x₆, there are only two remaining numbers to compare x₉ with. So we can find the absolute rank of x₉ in exactly two calls to rank.

The second part of the puzzle is to determine for an unknown series x of 80 numbers the maximum number of calls to rank(c(x₁,x₂,x₃)) to obtain rank(x). Of course, the dumb solution is to check all 82160 triplets, but I presume a sort of bubblesort would do better, even though Wikipedia tells me that bubble sort has worst-case and average complexity both О(n²), while quicksort has an average (if not worse-case) O(n log(n)) complexity…. If we follow the one-step procedure obtained in the first part to insert a new number, starting with three numbers whose relative rank is obtained with one  single call, we need in toto

1 + (9-3)*2 + ((1+3*8+2)-9)*3+(80-27)*4 =279

calls to rank since 80<1+3*(3*8+2)+2=81. (This is also the solution proposed in Le Monde, however there is no proof inserting one number at a time is the optimal solution.)