How to Learn Patience Sorting: Piles, Binary Search, Longest Increasing Subsequences and O(n log n) Reconstruction

Quick read: Patience sorting begins with a simple card-game rule: place each new value on the leftmost pile whose top is at least that value, or start a new pile if none exists. That tiny rule leads to an O(n log n) method for finding the length of a longest increasing subsequence and, with predecessor links, reconstructing an actual subsequence.

One-sentence answer: maintain the smallest possible tail value for an increasing subsequence of every length seen so far; binary search decides which tail a new value can improve.

Why patience sorting is a beautiful learning algorithm

Some algorithms feel invented from nowhere. Patience sorting is the opposite. You can act it out with cards, see the piles grow, notice that the pile tops remain ordered, and only then discover that the same structure encodes information about increasing subsequences.

That makes it unusually good for learning. A beginner can understand the physical rule. An intermediate programmer can implement the pile tops with binary search. An advanced learner can prove why the number of piles equals the length of a longest increasing subsequence. A professional can reason about reconstruction, duplicate policy, memory, streaming variants and how the same “best tail so far” idea appears in dynamic programming optimisation.

1. Begin with cards, not equations

Read a sequence from left to right. For each value x:

find the leftmost pile whose top is greater than or equal to x;
place x on that pile;
if no such pile exists, create a new pile on the right.

For the sequence [3, 1, 5, 2, 6, 4, 9], the visible pile tops evolve like this:

3 → [3]
1 → [1]
5 → [1, 5]
2 → [1, 2]
6 → [1, 2, 6]
4 → [1, 2, 4]
9 → [1, 2, 4, 9]

Four piles remain. The longest increasing subsequence has length four; for example, [1, 2, 4, 9].

2. The crucial reinterpretation: piles become tails

For algorithmic work, you usually do not store complete piles. Instead maintain an array tails. After processing some prefix of the input, tails[k] is the smallest ending value found so far for an increasing subsequence of length k + 1.

That sentence is the heart of the method. tails is not necessarily an actual subsequence. It is a compact summary of the best ending value available for each possible length.

Why prefer a smaller tail? Because a smaller ending value is easier to extend later. If two increasing subsequences have the same length and one ends at 7 while the other ends at 4, the one ending at 4 leaves more future values available as valid extensions.

3. Why binary search appears

The values in tails are increasing. Therefore, when a new value x arrives, we can binary-search for the first tail that is greater than or equal to x. Replace that tail with x. If x is larger than every tail, append it.

from bisect import bisect_left

def lis_length(values):
    tails = []
    for x in values:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Each of the n values performs one binary search over at most n tails, so the running time is O(n log n). The tails array uses O(n) space in the worst case.

4. Strictly increasing versus non-decreasing

Duplicate handling changes the problem. For a strictly increasing subsequence, use the first position whose value is >= x, usually called lower_bound or Python’s bisect_left. For a non-decreasing subsequence, use the first position whose value is > x, usually upper_bound or bisect_right.

This is not a minor implementation detail. It changes the mathematical definition being computed. Professional code should make the policy explicit in the function name, documentation and tests.

5. Why the number of piles gives the LIS length

There are two useful directions to the argument.

First: every time the algorithm creates a new pile on the right, the new value is larger than all existing pile tops. This certifies that an increasing subsequence one element longer can exist.

Second: the pile-placement rule prevents any increasing subsequence from being longer than the number of piles. Intuitively, values in an increasing subsequence must move through progressively later piles. An increasing subsequence cannot take two elements in increasing order from the same pile under the placement rule.

The result is that the number of piles exactly matches the length of a longest increasing subsequence. The classical literature connects patience sorting to rich combinatorics; for programming, the key lesson is that a greedy local replacement can preserve exactly the global information we care about.

6. Length is easy; reconstructing the subsequence takes bookkeeping

The short tails implementation returns only the length. To recover an actual LIS, store:

tails_idx[k]: the input index currently representing the best tail of length k + 1;
prev[i]: the predecessor index of input element i in the chosen subsequence.

from bisect import bisect_left

def longest_increasing_subsequence(a):
    if not a:
        return []

    tails_values = []
    tails_idx = []
    prev = [-1] * len(a)

    for i, x in enumerate(a):
        pos = bisect_left(tails_values, x)

        if pos == len(tails_values):
            tails_values.append(x)
            tails_idx.append(i)
        else:
            tails_values[pos] = x
            tails_idx[pos] = i

        if pos > 0:
            prev[i] = tails_idx[pos - 1]

    result = []
    k = tails_idx[-1]
    while k != -1:
        result.append(a[k])
        k = prev[k]

    result.reverse()
    return result

The reconstruction remains O(n) after the O(n log n) scan. The extra arrays are the price of returning a witness rather than only its length.

7. The subtle fact: `tails` itself is not generally the answer

This is the misconception worth testing deliberately. Replacements in tails can combine values that came from incompatible positions in the original sequence. The array is an optimisation summary, not a guaranteed path through the input.

This distinction appears throughout professional algorithms. A dynamic-programming table, a heuristic bound, a frontier and a summary sketch may contain enough information to compute an optimum without literally storing the optimum object. Learning to distinguish state used to solve from solution returned is an important step beyond beginner coding.

8. From O(n²) dynamic programming to O(n log n)

A natural first LIS solution uses dynamic programming: for every index i, inspect all earlier indices j and extend the best subsequence ending at a smaller value. That solution is excellent for learning because its state meaning is obvious, but it takes O(n²) time.

Patience sorting improves the bottleneck. Instead of remembering the best length ending at every earlier position, it keeps only the smallest known tail for each length. The ordered tails make binary search possible. This is a recurring algorithm-design pattern: identify which historical states are dominated, discard them, and organize the survivors so the next transition is faster.

9. Professional concerns: comparisons, objects and memory

Comparator semantics: if values are objects, define exactly what “increasing” means and ensure the ordering is consistent.
Duplicates: choose strict or non-decreasing semantics deliberately.
Witness requirements: if only the length is required, predecessor arrays are unnecessary overhead.
Streaming: LIS summaries can be maintained incrementally, but exact reconstruction requires retaining enough history.
Very large inputs: the asymptotic improvement from O(n²) to O(n log n) becomes decisive, but cache locality and allocation behaviour still matter.
Indices versus values: real applications often need original indices, timestamps or object references, not just the value sequence.

10. Testing the implementation

empty input → length 0;
one value → length 1;
strictly increasing input → length n;
strictly decreasing input → length 1;
all equal values → length 1 for strict LIS, length n for non-decreasing LIS;
random short arrays → compare O(n log n) results against a simple O(n²) reference implementation;
for reconstructed output, verify that indices increase and values satisfy the chosen ordering relation.

Differential testing against the slower, simpler dynamic-programming solution is especially valuable. A reference algorithm does not need to be fast if it is used only on small randomized inputs to validate a more complicated implementation.

11. A learning sequence that reduces memorisation

Start with the physical pile game. Predict where each card will go before running code. Next, replace the piles with only their top cards and explain what information has been lost and what has been preserved. Then introduce binary search. Only after that should you write the compact implementation.

This progression fits well with evidence from programming education: worked examples can reduce unnecessary cognitive load, subgoal labels can focus attention on why a code fragment exists, PRIMM-style prediction and modification encourage code reading before code generation, and Parsons problems can scaffold learners who are not yet ready to produce the whole program unaided.

12. Practice ladder: beginner to professional

Beginner: deal a sequence of ten numbers into piles by hand.
Developing: maintain only pile tops and explain why they stay sorted.
Intermediate: implement LIS length with binary search and state the meaning of every entry in tails.
Advanced: reconstruct one LIS using predecessor links and prove that the result is valid.
Professional: build strict and non-decreasing versions, differential-test them against an O(n²) oracle, benchmark on large inputs, and document comparator and duplicate semantics.

13. Why this algorithm transfers beyond LIS

The deepest lesson is dominance. For a fixed subsequence length, a larger tail is never more useful than a smaller tail if all future decisions depend only on whether a new value is larger. So the larger state can be discarded.

That is a general optimisation idea: compress a large state space by keeping only non-dominated representatives. Similar reasoning appears in dynamic programming, shortest paths, scheduling, Pareto frontiers and search. Patience sorting therefore teaches more than LIS; it teaches how to ask which past information the future genuinely needs.

Sources and further reading

Final idea: Do not memorize “use binary search for LIS.” Understand the compressed state: for every length, keep the smallest tail seen so far. Once that sentence is clear, the algorithm has a reason rather than a recipe.

Small Group Tutorials