Number of times we have to do an operation to sort "n" items

Question

Assume I have n objects with different (maybe random) weights. The objects are labeled from 1 to n, and they are not sorted.

I intend to sort the n objects based on their weights. The only tool I have is a scale with two plates by which I can compare the objects pair by pair, and register the pairs' results on a log. I wonder, in the worst-case scenario, how many times I have to do the weighing operation by the scale.

I thought about it hard, and I think the number of times I have to do the weighing operation is

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0

Therefore, the result would be (n-1)*n/2. Therefore the big O would be O(n2)

But I'm not sure about the correctness of my calculations. I wonder if anybody can suggest if this solution is wrong. If so, what is the correct answer.

---

My reasoning under the hood is that, for object number n, I have to compare it with n-1 objects, then I will be able to log how many objects are heavier/lighter than it. Therefore, I will know the position of object n among all the objects.

For object number n-1, I have to do the weighing operation with n-2 objects ... for object number 1 I have to do the weighing operation with 0 objects. Hence the total weighing operations might be:

(n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1 + 0

Answer 1

This is a standard result in computer science. You can use merge sort to perform at Θ(n log(n)) comparisons.

The proof that there's no asymptotically better method is as follows: the objects can be in n! different permutations initially, and a single weighing can at best halve the number of possibilities. So log2(n!) = O(n log2(n)) is a worst-case lower bound for the number of comparisons of any optimal sorting algorithm.

Answer 2

you can optimize the result. the result will be O(nlogn). but how? lets see, suppose you have balanced i object and sorted them already..

1, 2, 3 ,4 , ...... , i. 

now when you have to chose the (i+1)th you can use binary search. first choose the middle object from your chosen object, then compare with current object that have to be placed if it is heavier than the current object the object will placed in the left of the middle and otherwise it will placed in the right of the middle. so any ith object you need log(n) steps. So for n object you need O(nlogn) steps.