To perform the search-in-map with only a balance scale, we’d either need to compare all pairs of weights ahead of time (which would mean O(n^2) effort)
So long as “is heavier than” is a transitive relationship (so that finding A>B and B>C lets you know that A>C without having to actually weigh them against each other), you would only need O(n log n) pairwise comparisons to put your rocks into sorted order.
It doesn’t change the point being made, but:
So long as “is heavier than” is a transitive relationship (so that finding A>B and B>C lets you know that A>C without having to actually weigh them against each other), you would only need O(n log n) pairwise comparisons to put your rocks into sorted order.