TAOCP 5.2.1 Exercise 6
Let $R_1,\dots,R_N$ be the records, and let their final order after two-way insertion be determined as in Table 2, where each new record is inserted either to the left end or the right end of the curr...
Section 5.2.1: Sorting by Insertion
Exercise 6. [23] [23] The two-way insertion method illustrated in Table 2 seems to imply that there is an output area capable of holding up to $2N + 1$ records, in addition to the input area containing N records. Show that two-way insertion can be done using only enough space for $N + 1$ records, including both input and output.
Verified: yes
Solve time: 1m27s
Solution
Let $R_1,\dots,R_N$ be the records, and let their final order after two-way insertion be determined as in Table 2, where each new record is inserted either to the left end or the right end of the current sequence, depending on comparisons.
The apparent storage model in Table 2 maintains a contiguous block that can expand in both directions, which suggests a layout requiring $2N+1$ positions. The goal is to realize the same sequence of states using only $N+1$ storage cells.
Label a linear array $A[0],A[1],\dots,A[N]$ of size $N+1$. Arithmetic on indices is performed modulo $N+1$. At all times the stored records occupy exactly $j$ distinct positions after $j$ insertions, so at least one array position remains empty.
After the first record is placed, choose an arbitrary index $p_1 \in {0,\dots,N}$ and set $A[p_1] = R_1$. For $j \ge 2$, suppose the records $R_1,\dots,R_{j-1}$ occupy distinct indices forming a cyclic interval in the sense that starting from the current leftmost occupied position and moving forward modulo $N+1$ visits each occupied cell exactly once.
Let $L$ denote the index of the leftmost occupied position and $R$ the index of the rightmost occupied position in this cyclic ordering. When inserting $R_j$, the two-way insertion rule determines whether it is placed to the left of $L$ or to the right of $R$ after comparisons with previously inserted keys, exactly as in Table 2.
If $R_j$ is inserted on the right, set $R \leftarrow (R+1) \bmod (N+1)$ and assign $A[R] \leftarrow R_j$. If $R_j$ is inserted on the left, set $L \leftarrow (L-1) \bmod (N+1)$ and assign $A[L] \leftarrow R_j$. Since at most $j-1 \le N-1$ positions are occupied before the insertion, the set of occupied indices cannot fill all $N+1$ cells, so the newly chosen position is always unoccupied and no overwriting occurs.
The relative order of records is preserved because the algorithm never reorders existing elements; each insertion extends the current linear order by placing the new element strictly beyond the current endpoints in the direction dictated by the two-way comparison process. The traversal starting at $L$ and advancing modulo $N+1$ yields exactly the same sequence as the explicit expanding array in Table 2, since both constructions maintain identical endpoint extensions at each step.
The storage requirement is therefore exactly $N+1$ cells for the array $A$, together with a constant amount of additional storage for $L$ and $R$. This replaces the $2N+1$ cells suggested by a naive two-sided unbounded layout.
Since $N$ distinct records must be stored simultaneously and one additional position is necessary to distinguish full from empty configurations in a cyclic representation, no representation using fewer than $N+1$ array cells can support arbitrary sequences of insertions without ambiguity between full and empty states. Hence $N+1$ cells are sufficient and necessary for this implementation.
This completes the proof. ∎