1,448 views
10 votes
10 votes
Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of $a, b, c, d$.

2 Answers

Best answer
11 votes
11 votes

It will be merge sort.

$a,b,c,d$

$1+1$ comparisons for lowest step

$+3$ comparisons for upper one

So, total $5$ comparisons


 

selected by
3 votes
3 votes
Requirements :  Pair wise sorting algo & min no of comparisons.
Ans : Merge sort

Related questions

2 votes
2 votes
0 answers
2
go_editor asked Jun 3, 2016
352 views
Consider six distinct points in a plane. Let $m$ and $M$ denote the minimum and maximum distance between any pair of points. Show that $M/m \geq \sqrt{3}$.
2 votes
2 votes
1 answer
3
go_editor asked Jun 3, 2016
750 views
The numbers $1, 2, \dots , 10$ are arranged in a circle in some order. Show that it is always possible to find three adjacent numbers whose sum is at least $17$, irrespec...
1 votes
1 votes
0 answers
4