# Comparison Sort Lower Bound

Bart Massey

### Introduction: Information Theory

• Super-neat subject, way outside scope for this course

• Here's one basic idea, though:

• Imagine you have a set S

• You can ask a binary (true/false) question about any subset T of S that will partition T into two subsets T1 and T2

• In the best case, how many questions does it take to find a specific element e of S by this process?

• Answer: lg |S|, by binary search, since the best that can be done is even divisions

• Thus BINARY FIND ELEMENT is in Ω(lg |S|)

### Comparison Is A Binary Operation

• Imagine we want to sort a sequence s of length n by binary comparison of elements. Let S be the set of all permutations of s

• |S| = n!

• A comparison of two elements of S is a binary operation on S, so the previous lower bound holds

• So, if we think of comparison sorting as selecting the correct permutation of s from the set of all permutations via binary search we must have at least m comparisons where

``````  m in Ω(lg |S|) = Ω(lg (n!))
= Ω(lg (sqrt(2 pi n) (n/e)^n))
= Ω(lg (sqrt(2 pi n)) + lg ((n/e)^n))
= Ω(lg n) + Ω(n lg n)
= Ω(n lg n)
``````

by Stirling's Approximation

### Problem Of The Day: Dutch Flag

• Given two values v1 and v2, in-place partition an array a such that for array indices k1 and k2

``````* i < k1 => a[i] <= v1
* i > k2 => a[i] >= v2
* v1 < a[i] < v2 otherwise
``````

Your algorithm should run in O(|a|) time and O(1) space, using only swaps and comparisons

• Bonus Problem: Rainbow Flag

Same thing, but partition a by v1, v2..vp, returning array indices k1, k2..kp with the same properties holding, where p is some constant

Your solution should still run in O(|a|) time and O(1) space

• Bonus Problem: Waving Rainbow Flag

Same thing, but instead of a constant p, we now have a variable number of values in an array v and return an array of indices k

Your solution should run in O(|a|^2) time and O(1) space