Patience sorting

Patience sorting processes values into piles by putting each next value on the leftmost pile whose top is at least that value, creating a new pile when none qualifies. The pile tops stay increasing, so binary search finds the destination. The number of piles equals the length of a longest increasing subsequence: each pile is nonincreasing in arrival order, while predecessor links across piles construct an increasing subsequence of that length. For 3,1,2,4, the tops evolve to 1,2,4, giving length three. Changing the comparison changes whether equality is allowed in the subsequence. Merging the completed piles can then produce a full sorted output.^[ref]

A pile top in patience sorting is the currently exposed value on one pile. With the rule “place the next value $x$ on the leftmost pile whose top is at least $x$,” pile tops remain strictly increasing from left to right. Replacing the chosen top preserves that invariant: all earlier tops are smaller than $x$, and later tops exceed the old chosen top and hence $x$.

More strongly, top $i$ is the smallest possible last value of an increasing subsequence of length $i+1$ among the entries seen so far. A smaller last value leaves more options for extending that subsequence. For 3,1,2, the top arrays are [3], [1], [1,2]. binary search finds each replacement position in logarithmic time. The final top array gives the length but need not itself be a subsequence: 2,3,1 ends with tops [1,3], although1 appeared after3. Predecessor pointers are needed to reconstruct a witness.