 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]

Patience sorting is a method used in combinatorial problems, particularly in sorting and card games, to find the longest increasing subsequence (LIS) of a sequence of numbers. The technique is named after the card game "patience," also known as solitaire. ### How Patience Sorting Works: 1. **Initial Setup**: Consider a sequence of numbers (or cards) that you want to sort or analyze for increasing subsequences.