# sorting of unordered elements - worst case scenario

• Apr 10th 2011, 10:43 AM
kaspers
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
• Apr 10th 2011, 02:14 PM
emakarov
Each comparison-based sorting algorithm has the worst complexity of \$\displaystyle \Omega(n\log n)\$. (For big-Omega and similar notations see this Wikipedia page.) For a proof, see these (PPT) or these (PDF) lecture slides or Google for 'sorting algorithm worst case nlogn "decision tree"'.
• Jan 7th 2012, 08:24 AM
kaspers
Re: sorting of unordered elements - worst case scenario
Thanks, that gave a complete answer to my question.