Sorting by k-ary Comparisons (2010)

Originators: Immanuel McLaughlin    (presented by Immanuel McLaughlin - REGS 2010)

Definitions: Given an unknown linear ordering T, a k-ary comparison returns the linear ordering among k specified elements from T. Let S(n,k,t) be the minimum number of k-ary comparisons needed to guarantee determining the top t elements of T in order.

Background: The case k=2 reduces to traditional binary comparison sorting, about which much is known (see [K], for example). Optimal algorithms are known for S(n,2,t) when t≤3, and asymptotically optimal algorithms are known for larger values of t.

Problem 1: Compute S(n,k,t), at least asymptotically.

Comments: A straightforward generalization of the optimal algorithm for finding the top two elements when k=2 yields S(n,k,2) ≤ (n-1)/(k-1)⌉ + ⌈logkn⌉-1. For k=2, equality holds. The next step is to find a lower bound. Aigner [A1] provided an approach for proving lower bounds. REGS 2010 participants produced algorithm for the case k ≤ t, but it is only asymptotically optimal even for the relatively simple case (k,t)=(2,3). Aigner [A2] found an optimal algorithm for this case; generalizing his algorithm for all (k,t) would be an obvious next step.

Problem 2: How many k-ary comparisons are needed to guarantee finding the s-th largest element of T?

Comments: This problem also is much studied for k=2, Again, generalizing known results for k=2 should offer a good starting point.

[A1] M. Aigner, Producing posets, Discrete Math. 35 (1981) 1-15.
[A2] M. Aigner, Selecting the top three elements, Discrete Appl. Math. 4 (1982) 247-267.
[K] D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching (Addison-Wesley, Reading, MA 1973).
L. Hyafil, Bounds for selection, SIAM J. Comput. 5 (1976) 109-l 14.