Search code examples
arrayssortinglogic

if you can sort 5 numbers in 7 comparisons, how to sort 6 numbers in 10 comparisons?

There is another question on sorting 5 numbers in 7 comparisons:

Sorting an array with minimal number of comparisons

My question is about sorting 6 numbers in 10 comparisons.

Solution

  • You can do it in 12 trivially:

    • Sort the first 5 numbers with 7 comparions
    • Compare the final number with each of the first 5, to determine its position

    You could do it in better than that using a binary search, of course... compare the final number with the middle of the 5, then with the first two or last two depending on the result of that comparison. This should end up with 10 comparisons at most.