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.
1 Answer
Changing the base of a logarithm is equivalent with just multiplying the expression by a constant: logb(n!) = loga(n!)/loga(b).
Since loga(b) is just a constant, algorithms with the complexity of j logk(n!) for any constants j and k solve the question (we just put c = jk).
For this reason the base of algorithms is usually ignored when discussing asymptotic complexity. We are basically looking for an algorithm in O(log(n!) = O(n log(n)).
There are known algorithms to solve your problem in this time, such as MergeSort or HeapSort.
The option to use an oracle that finds smallest number in a subset of k elements (rather than 2) only improves the possible algorithms by a constant.
I like the idea of a modified MergeSort that splits the balls into k subsets, sorts each of them recursively and uses your Oracle to merge these subsets in linear time.
But again, this is only a constant improvement over regular MergeSort (the depth of the recursion is logk(n) rather than log2(n)).
-
1$\begingroup$ The idea you describe is also a well-known solution, named a 'multi-way merge sort' or 'N-way merge' etc. It's been devised for external sorting in the old times of tape storage to utilize multiple (4 or more) storage units simultaneously for sorting data. See e.g. the Wikipedia article 'K-Way Merge Algorithms', a StackOverflow thread Algorithm for N-way merge, or ask Google for 'multi-way merge sort'. $\endgroup$– CiaPanOct 26, 2016 at 7:22