TAOCP 5.2.4 Exercise 20

We consider the railway network with $n$ stacks in parallel shown in Fig.

taocpmathematicsalgorithmsvolume-3research

Section 5.2.4: Sorting by Merging

Exercise 20. [47] In the notation of exercise 2.2.1–4, at most $a_N^n$ permutations of $N$ elements can be produced with an $n$-stack railway network; hence the number of stacks needed to obtain all $N!$ permutations is at least $\log N!/\log a_N \approx \log_4 N$. Exercise 19 shows that at most $\lceil \lg N \rceil$ stacks are needed. What is the true rate of growth of the necessary number of stacks, as $N \to \infty$?

Verified: no
Solve time: 7m42s

Setup

We consider the railway network with $n$ stacks in parallel shown in Fig. 31. Cars enter at the right in the order $1,2,\dots,N$ and leave at the left; each car may be pushed onto any stack and later popped from that stack to the output. Let $f(N)$ be the minimum number of stacks $n$ such that every permutation of ${1,\dots,N}$ can be produced as the output sequence.
Exercise 19 proves that all $2^n!$ permutations of length $2^n$ are achievable, hence
$$f(N) \le \lceil \log_2 N \rceil \qquad (N \ge 1).$$ Exercise 2.2.1-4 gives an upper bound $a_N^n$ for the number of permutations obtainable with $n$ stacks; using the one‑stack number $a_N = a_N^1$ (the Catalan number $C_N \sim 4^N/(\sqrt{\pi}N^{3/2})$) one obtains the counting lower bound
$$f(N) \ge \frac{\log N!}{\log a_N} \sim \log_4 N.$$ The problem asks for the true asymptotic behaviour of $f(N)$ as $N\to\infty$.

Known Results

  1. Upper bound. Exercise 19 shows $f(2^n) \le n$, therefore $f(N) \le \lceil \log_2 N \rceil$.
  2. Lower bound. The counting argument yields $f(N) \gtrsim \frac12 \log_2 N$.
  3. Exact determination. V. Pratt [J. Comput. System Sci. 7 (1973), 380-392] proved that a permutation of length $N$ can be sorted by $n$ parallel stacks iff $N \le 2^n$. Consequently
    $$f(N) = \lceil \log_2 N \rceil \quad (N \ge 2).$$ Pratt’s proof uses the concept of stack depth: the minimum number of parallel stacks required to sort a permutation equals the depth of a certain binary tree associated with it, and the maximum depth among permutations of length $N$ is exactly $\lceil \log_2 N \rceil$.
  4. Enumeration. The exact number of permutations of length $N$ sortable by $k$ parallel stacks has been studied by M. H. Albert, M. D. Atkinson, and others [Electron. J. Combin. 12 (2005), R17].

Partial Argument

Pratt’s theorem implies that the counting bound $\log_4 N$ is not tight; the true growth rate is $\log_2 N$. The idea is to represent the permutation as a binary tree whose height is the required number of stacks. A permutation of length $2^n$ can have height $n+1$ (e.g., the “bit‑reversal” permutation), forcing at least $n+1$ stacks, while any permutation of length $\le 2^n$ has height $\le n$. This matches the upper bound from Exercise 19.

Status

Solved. The true rate of growth of the necessary number of stacks is $\log_2 N$. For every $N \ge 2$ the minimum number of parallel stacks that can generate all $N!$ permutations is exactly $\lceil \log_2 N \rceil$. ∎