12 Distinct Weights' Sorting

Question

There are 12 balls with all different weights. You want to sort these balls by weight. You have a friend who will help you with the ordering process. In each step, you give any 4 balls to your friend and your friend returns their exact weight order without telling their actual weight.

What is the minimum number of measurements do you need in order to guarantee to sort the balls correctly by weight?

Reference: http://www.puzzleup.com/2019/puzzle/?71

Answer 1

For the sake of this example, I assume a ball to be removed from the set once its position has been identified.

I got it in 10 steps. (Thanks for the improvements)

Steps 1-3:

Select balls randomly, four at a time, and have them sorted into 3 groups in ascending weight. Call these sets S1, S2, and S3.

Step 4:

Select the lightest ball from each group. Select the second lightest ball from one of the groups, at random. Compare those 4. Worst case scenario, you have now removed 1 ball (L1) from your set of 12. For the sake of example, L1 was selected from S1. S1 now has only 3 balls remaining.

Step 5:

Repeat step 4, but for the heaviest ball in each set, and a random second-heaviest ball. You can now identify the heaviest ball from the group (L12)

Step 6:

We can now run double tests with each experiment. Select the the lightest remaining ball from step 4 and the lightest remaining ball from the set that contained L1. Select the heaviest remaining ball from step 5 and the heaviest ball from the set that had contained L12. Compare those four. The heaviest of those 4 is confirmed to be L11. The lightest is confirmed to be L2.

Step 7:

Essentially a repeat of step 6. Compare the lightest ball from step 4 with the next lightest ball from the set that contained L2. Compare the heaviest remaining ball from step 5 with the next heaviest ball from the set that contained L11. You will now be able to confirm L3 and L10.

Step 8/9:

Now it gets a little bit tricky. We are assuming the worst case scenario, so that means that L1 and L2 were the lightest respective balls in two different sets and L12 and L11 were the heaviest respective balls in two different sets. We now have 3 candidates for the heaviest ball and 3 candidates for the lightest ball that were never compared to one another, so we cannot draw any conclusions. As such, we now have to compare the heaviest balls in each set (plus a random second-heaviest ball in a set) and the lightest balls in each set (plus a random second-lightest ball in a set). Each of those steps will allow us to eliminate one additional ball. (L4 and L9).

Step 10)

Weigh the four remaining balls. They will comprise L5, L6, L7, and L8. All balls are in order.

Please note that this solution may exit differently and take different logic in non-worst-case scenarios.