# 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 FlagSame 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 FlagSame 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