# sort n balls by knowing the lightest in one query

Suppose there are $n$ balls with different weights and let $b$ be an integer between $2$ and $n$. There is a machine which, given a set $S\subset\{1,2,3,\dots,n\}$ of size at most $b$, can tell you the lightest ball in $S$. Goal is to sort the $n$ balls according to their weights, using only fewest queries to the machine. Find an algorithm to solve it using $c\log_b(n!)$ queries, for some constant $c$. where c is an absolute constant independent of b and n.

• What if we solve the problem in O(1/n) time? – greenturtle3141 Oct 26 '16 at 4:40
• how will you do that ... ? – user1815760 Oct 26 '16 at 7:19