Patience sorting places each card on the leftmost pile whose top card is ≥ the new card.
If no pile qualifies, start a new pile. The top cards across piles always form a strictly increasing sequence.
The number of piles at the end equals the length of the longest increasing subsequence (LIS).
Original sequence:
Enter a sequence and press Sort.
Piles will appear here.
Erdős–Szekeres theorem: Any sequence of more than n² distinct numbers contains either an increasing subsequence of length > n or a decreasing subsequence of length > n. Equivalently, any sequence of n²+1 numbers has a monotone subsequence of length ≥ n+1.
Try it: choose n and generate a random sequence of n²+1 numbers. The algorithm finds a monotone (increasing or decreasing) subsequence of length ≥ n+1 — guaranteed by the theorem.
Sequence (n²+1 numbers):
Proof sketch via patience sorting: When you run patience sorting, the number of piles = LIS length. If there are ≤ n piles, by pigeonhole some pile has ≥ n+1 cards — and those form a decreasing subsequence! So either LIS ≥ n+1 (blue) or LDS ≥ n+1 (red).