Patience Sort and the Longest Increasing Subsequence

The problem it solves

Given a sequence of n numbers, the Longest Increasing Subsequence is the longest list of elements — not necessarily contiguous — that appears in increasing order. In [3, 1, 4, 1, 5, 9, 2, 6] one LIS is [1, 4, 5, 9] (length 4). LIS is a canonical dynamic programming exercise, but the textbook DP is O(n^2): for each element you scan all earlier elements to extend the best run.

Patience sort attacks the same problem through a solitaire metaphor. You deal cards one at a time onto a row of piles under a single constraint borrowed from the card game patience (British for solitaire): a card may only be placed on a pile whose top card is greater than or equal to it. Greedily minimizing the number of piles turns out to compute the LIS length directly, and — with a little bookkeeping — the LIS itself. The payoff is dropping from quadratic to O(n log n), which is the difference between seconds and hours on a million-element input.

How it works, step by step

Maintain a list of piles, represented by their top cards. Process each value x left to right:

• Find the leftmost pile whose top is ≥ x. Because pile tops are always sorted, this is a binary search.
• If found, replace that pile's top with x (x becomes the new, smaller tail).
• If none exists (x is bigger than every top), start a new pile on the right.

The array of pile tops is exactly the classic tails array of the O(n log n) LIS DP: tails[k] holds the smallest possible tail value of any increasing subsequence of length k+1. To recover the actual subsequence, store a back-pointer: when x lands on pile k, point it at the current top of pile k-1. At the end, follow pointers from the top of the last pile.

for x in seq:
    k = bisect_left(tails, x)   # strictly-increasing LIS
    if k == len(tails): tails.append(x)
    else: tails[k] = x
    parent[x_index] = pile_top_index[k-1] if k>0 else -1
return len(tails)              # = LIS length

Use bisect_left for a strictly increasing LIS; bisect_right for non-decreasing.

Complexity and a worked trace

Each of the n elements triggers one binary search over at most n piles: O(log n) each, so O(n log n) total in the best, average, and worst case. Space is O(n) for the tails array plus O(n) for back-pointers if you reconstruct. There is no bad input — the bound is unconditional, unlike quicksort's O(n^2) worst case.

Trace [3, 1, 4, 1, 5, 9, 2, 6], strictly increasing, showing tails after each step:

x=3 -> [3]
x=1 -> [1]          # 1 replaces 3 (pile 0)
x=4 -> [1,4]        # new pile
x=1 -> [1,4]        # 1 replaces top of pile 0
x=5 -> [1,4,5]      # new pile
x=9 -> [1,4,5,9]    # new pile
x=2 -> [1,2,5,9]    # 2 replaces 4 (pile 1)
x=6 -> [1,2,5,6]    # 6 replaces 9 (pile 3)

Final length = 4 piles ⇒ LIS length 4. Note the tails array [1,2,5,6] is not itself a valid subsequence of the input — it mixes elements from incompatible positions. That is why back-pointers, not the tails snapshot, must be used to output the real LIS (e.g. [1,4,5,9]).

Where it shows up in real systems

The most famous production use is text diffing. Computing a minimal diff between two files reduces to a Longest Common Subsequence, and the Hunt–Szymanski algorithm converts LCS into an LIS problem, then solves it with patience-sort-style binary search. Variants of this power git diff's patience diff and histogram algorithms, which anchor on unique lines and run patience sort to align the rest — producing cleaner, more human-readable diffs than the classic Myers algorithm on refactored code.

• Version control and merge tools: Git, Bazaar, and IDE three-way merges use patience/LIS matching to reduce spurious hunks.
• Competitive programming and interviews: the default O(n log n) LIS solution.
• Combinatorics and probability: pile counts connect to the RSK correspondence and Young tableaux; Aldous and Diaconis used patience sort to explain why a random permutation's LIS length concentrates near 2√n, with fluctuations following the Tracy–Widom distribution.
• Bioinformatics: chaining collinear seed matches in genome aligners is an LIS problem.

Patience sort vs. the alternatives

Against the quadratic DP, patience sort wins asymptotically (O(n log n) vs O(n^2)) while using the same O(n) space, and it reconstructs the LIS just as easily via parent pointers. The DP is only preferable when n is tiny or when you need per-index "length of LIS ending here" values for a downstream computation.

Do not confuse patience sort with a general-purpose sorting algorithm. Although you can sort by merging the sorted piles (each pile is decreasing, so repeatedly extract the global minimum with a heap), that merge step is what makes real sorting O(n log n); the piling phase alone does not sort — it counts monotone structure. Compared with merge sort, patience sort's real value is not ordering data but revealing the longest monotone run.

• Fenwick/BIT variant: index tails by value instead of length to answer constrained or counting LIS queries.
• vEB trees: shave the log to O(n log log n) only for small integer universes — rarely worth the constants.

Pitfalls, failure modes, and significance

The classic bug is emitting the tails array as the answer. As the trace showed, tails holds minimal tail values from possibly-incompatible positions; its length is correct but its contents are not a subsequence. Always reconstruct via back-pointers.

• Strict vs. non-strict: bisect_left gives a strictly increasing LIS; bisect_right gives longest non-decreasing. Picking the wrong one silently off-by-ones on inputs with duplicates.
• Longest decreasing subsequence: negate the values (or reverse the comparator), don't rewrite the loop.
• Comparator correctness: on custom keys, an inconsistent comparator breaks the sorted-tails invariant and the binary search returns garbage.

Historically, patience sorting was named by C.L. Mallows, who credited its invention to A.S.C. Ross in the early 1960s; Hammersley first noted it computes LIS length, and the 1999 survey by Aldous and Diaconis cemented its place linking a children's card game to deep results in random matrix theory. Few algorithms are simultaneously a one-page interview answer and a bridge to the Baik–Deift–Johansson theorem.

LIS approaches compared: naive DP vs. patience sort vs. related methods

Method	Time	Space	Notes
Quadratic DP (dp[i]=longest ending at i)	O(n^2)	O(n)	Simplest; also yields LIS via parent array
Patience sort (tails + binary search)	O(n log n)	O(n)	Greedy leftmost pile; reconstructs LIS with back-pointers
Patience sort + Fenwick/BIT (value-indexed)	O(n log n)	O(n)	Handles LIS-with-constraints / counting variants
Van Emde Boas / y-fast tries	O(n log log n)	O(n)	Only for small integer universe; large constants
Full sorting of the array	O(n log n)	O(n)	Solves nothing about LIS — different problem