sorting of unordered elements - worst case scenario
Hi, I have a problem which seems easy but is giving me a hard time, I'd really appreciate some input.
Assuming I have n objects and have to put them in order, how many comparisons between each 2 objects do I have to make in the worst case scenario?
I made some attempts but find it difficult to come up with a generic formula (Headbang)
1 object -> 0 comparisons
2 objects -> 1 comparison suffices
3 objects -> first do 2 objects (1 comparison) and then compare remaining object with bigger/smaller element (1 comparison), if smaller/bigger then compare with the remaining object (1 comparison). In total 3 steps.
4 objects -> as in 3 objects (3 comparisons), then compare remaining object with the middle point. If it's smaller/bigger then compare with smallest/largest element. Total of 3+2=5 steps
5 objects -> as in 4 objects (5 comparisons). Find the middle point (2nd or 3rd object, 1 comparison). It's the last step of ordering 3 objects (when 2 are already ordered and we need to find the place of the final element, 2 steps). Total of 5+1+2=8 comparisons.
Generally the story is: Use the number of steps used for n-1. Then find the middle of the n-1 string (if it's even it does not matter whether I take (n-1)/2 or (2+1)/2). Then find the middle of this string and repeat the process until we are left with case of ordering 2 objects.
Please tell me if the general formula for this exist and if so I'd appreciate any hints
Re: sorting of unordered elements - worst case scenario
Thanks, that gave a complete answer to my question.