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