= 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.https://www.stat.berkeley.edu/users/aldous/Research/OP/patience.pdf[Aldous and Diaconis, patience sorting and increasing subsequences]{ref}
Back to article page
