0
$\begingroup$

Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can return anything, even a completely unsorted array.)

I know that using comparison model of sorting algorithms there is a lower bound of $\Omega(n \log n)$ so I try to make a proof by contradiction and to get to the fact that if such an algorithm exist then we can sort by comparison sort in linear time.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Suppose that a comparison-based sorting algorithm sorts the set of permutations $\Pi$ correctly. Construct the comparison decision tree underlying the algorithm, with permutations as leaves. Each permutation in $\Pi$ must appear as a leaf (why?), hence the tree must have depth at least $\log_2 |\Pi|$ (why?).

$\endgroup$
0
$\begingroup$

There are n! possible permutations of n items, which is why we need $\log_2(n)$ comparisons, rounded up to the next integer since we can't have half a comparison, to distinguish them. That number is quite close to $n \cdot \log_2(n / e)$. To sort half of the possible inputs, we need ONE fewer comparison. To get to linear time, we have to restrict the number of inputs a lot more.

On the other hand, we can sort an array for example in 100n comparisons when $\log_2(n / e) < 100$ or $n/e < 2^{100}$ or $n < e \cdot 2^{100}$. The largest computer that I can't afford to buy would sort any array that I could store in memory in 40n comparisons.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.