title: Comparison Sort - Theoretical
body: <p>Can someone explain the solution of this problem to me?</p>
  
  <p>Suppose that you are given a sequence of <em>n</em> elements to sort. The input sequence
  consists of <em>n=k</em> subsequences, each containing <em>k</em> elements. The elements in a given
  subsequence are all smaller than the elements in the succeeding subsequence and
  larger than the elements in the preceding subsequence. Thus, all that is needed to
  sort the whole sequence of length <em>n</em> is to sort the <em>k</em> elements in each of the <em>n=k</em>
  subsequences. Show an <em>n lg k</em> lower bound on the number of comparisons
  needed to solve this variant of the sorting problem.</p>
  
  <p>Solution:</p>
  
  <p>Let <em>S</em> be a sequence of <em>n</em> elements divided into <em>n/k</em> subsequences each of length <em>k</em>
  where all of the elements in any subsequence are larger than all of the elements
  of a preceding subsequence and smaller than all of the elements of a succeeding
  subsequence.</p>
  
  <p>Claim</p>
  
  <p>Any comparison-based sorting algorithm to sort <em>S</em> must take <em>(n lg k)</em> time in the
  worst case.</p>
  
  <p>Proof</p>
  
  <p>First notice that, as pointed out in the hint, we cannot prove the lower
  bound by multiplying together the lower bounds for sorting each subsequence.
  That would only prove that there is no faster algorithm that sorts the subsequences
  independently. This was not what we are asked to prove; we cannot introduce any
  extra assumptions.</p>
  
  <p>Now, consider the decision tree of height h for any comparison sort for S. Since
  the elements of each subsequence can be in any order, any of the <em>k!</em> permutations
  correspond to the final sorted order of a subsequence. And, since there are <em>n/k</em> such
  subsequences, each of which can be in any order, there are <em>(k!)^n/k</em> permutations
  of S that could correspond to the sorting of some input order. Thus, any decision
  tree for sorting S must have at least <em>(k!)^n/k</em> leaves. Since a binary tree of height <em>h</em>
  has no more than <em>2^h</em> leaves, we must have <em>2^h ≥ (k!)^(n/k)</em> or <em>h ≥ lg((k!)^n/k)</em>. We
  therefore obtain</p>
  
  <pre><code>     h ≥ lg((k!)^n/k)          -- unbalanced parens - final one added?
         = (n/k) lg(k!)
         ≥ (n/k) lg((k/2)^k/2)
         = (n/2) lg(k/2)
  </code></pre>
  
  <p>The third line comes from <em>k!</em> having its <em>k/2</em> largest terms being at least <em>k/2</em> each.
  (We implicitly assume here that k is even. We could adjust with floors and ceilings
  if <em>k</em> were odd.)</p>
  
  <p>Since there exists at least one path in any decision tree for sorting S that has length
  at least <em>(n/2) lg(k/2)</em>, the worst-case running time of any comparison-based sorting
  algorithm for S is <em>(n lg k)</em>.</p>
  
  <p>Can someone walk me through the steps in code block? Especially the step when <em>lg k!</em> becomes <em>lg((k/2)^k/2)</em>.</p>