+18 votes
1k views
The minimum number of comparisons required to sort $5$ elements is ____
asked
edited | 1k views

Some Important points from wiki -->

https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

• If the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2f(n) cases because the keys are distinct and each comparison has only two possible outcomes.
• Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known.

## 1 Answer

+23 votes
Best answer

Answer: 7

Minimum number of comparisons = $\lceil \log(n!) \rceil$ =  $\lceil \log(5!) \rceil$ = $\lceil \log(120) \rceil$ = 7.

Ref: http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

answered by Veteran (35.9k points)
edited by
See the above link. The technique is given by Knuth :)
But of array is sorted and i use insertion sort it will take 4 comparisions?
Yes if we use insertion sort on already sorted array of n it takes n-1 comparisons.
Yes.
even bubble sort on already sorted array will give 4 comparisons right ?
@Arjun sir, here we are answering for the worst case, right? Otherwise, if array is sorted and I use insertion sort it will take 4 comparisions, right?
I am also getting 4 as answer as minimum comparison is being asked.
Answer:

+11 votes
3 answers
1
+20 votes
3 answers
2
+6 votes
2 answers
3