Patience Sort: When and How to Use It

1. Introduction and Core Concepts

Patience sort is a distinctive sorting algorithm inspired by the card game Patience, more commonly known as Solitaire. Unlike traditional comparison-based sorts that operate by swapping or merging elements in place, patience sort organizes data into piles according to a simple set of rules that mimic how a player would sort cards into piles on a table. It was first described in its modern algorithmic form by Alden H. Wright, John W. Griggs, and others in the early 1960s, though its underlying principle was studied by mathematicians like C. Schensted in the context of combinatorics and permutation theory.

At its heart, patience sort is not just a sorting method but a powerful technique for understanding the structure of permutations. Its most celebrated property is its intimate connection to the Longest Increasing Subsequence (LIS) problem. The number of piles created during the first phase of patience sort is exactly equal to the length of the longest decreasing subsequence, and by a simple modification, the length of the longest increasing subsequence. This duality makes it far more than a curiosity; it is a fundamental tool in combinatorics, probability theory, and algorithm design.

Why does patience sort matter today when we have highly optimized algorithms like Timsort and Introsort built into standard libraries? The answer lies in its unique performance profile. Patience sort excels when the input data is already partially ordered or contains long naturally sorted runs. It is stable, can be implemented to be highly efficient for nearly-sorted data, and its pile structure provides valuable information about the input beyond just a sorted output. For developers working with streaming data, external sorting, or problems that reduce to finding increasing subsequences, understanding patience sort provides both a practical sorting strategy and a conceptual framework for tackling a broader class of problems.

Conceptually, patience sort operates in two distinct phases. The first phase deals cards into piles, where each pile is maintained in decreasing order from bottom to top. A new card can only be placed on the leftmost pile whose top card is greater than or equal to the new card; if no such pile exists, a new pile is created to the right. The second phase merges these piles back together into a single sorted sequence, typically using a k-way merge with a priority queue. This two-phase approach gives the algorithm its characteristic behavior and its interesting complexity trade-offs.

2. How It Works

The mechanics of patience sort are best understood through its card game analogy. Imagine you are dealt a shuffled deck of cards one by one, face up. You must arrange them into piles on a table following one strict rule: you may place a card on top of a pile only if that pile's top card has a value greater than or equal to the new card. If you cannot place the card on any existing pile, you must start a new pile to the right of all existing piles. The goal is to use as few piles as possible, which requires always choosing the leftmost eligible pile.

This greedy choice is the critical insight. By always placing each card on the leftmost possible pile, the algorithm ensures that the top cards of the piles remain sorted in increasing order from left to right. This invariant is what allows the pile-finding step to be optimized with binary search. For example, if the pile tops are [3, 7, 11] and the next card is 5, the leftmost pile with a top greater than or equal to 5 is the pile topped with 7. Placing 5 there maintains the sorted order of pile tops as [3, 5, 11]. This property is formally a consequence of Dilworth's decomposition theorem and is essential for efficiency.

The first phase continues until all cards have been dealt into piles. At this point, each individual pile is internally sorted in decreasing order (because we only ever place smaller or equal cards on top of larger ones), but the collection of piles as a whole is not sorted. The second phase is where the actual sorting happens. To produce the final sorted output, we repeatedly extract the smallest visible card among all pile tops. Since each pile is sorted, the smallest remaining card overall must always be one of the current pile tops. By using a min-heap to efficiently find the minimum top card, we can merge the piles in sorted order.

The Two Phases in Detail

Phase 1: Distribution into Piles. For each element x in the input array, perform a binary search over the current pile tops to find the leftmost pile where top >= x. If found, push x onto that pile; otherwise append a new pile [x]. This phase is O(n log n) in the worst case due to the binary search, but can be much faster if the number of piles remains small.

Phase 2: K-Way Merge. Initialize a min-heap with the top element of each pile along with its pile index. Repeatedly pop the smallest element from the heap, append it to the output array, and if the pile it came from still has elements, push its new top onto the heap. This merge is analogous to the merge step in merge sort but operates on p piles where p can be much smaller than n for partially sorted inputs.

• Invariant 1: Each pile is strictly decreasing from bottom to top.
• Invariant 2: The top cards of the piles are strictly increasing from left to right.
• Key Optimization: Invariant 2 allows binary search in Phase 1 instead of linear scan.
• Stability: If the rule is top > x (strictly greater) for placement, the sort can be made stable.

It is important to distinguish patience sort from patience sorting for LIS. If you only need the length of the longest increasing subsequence, you can discard the full piles and only keep the pile tops, which reduces space to O(n) in the worst case but typically much less. The full sorting algorithm requires storing all elements in piles.

3. Implementation

Implementing patience sort in Python is straightforward and provides an excellent exercise in combining binary search with heap-based merging. The naive implementation that scans piles linearly for each card runs in O(n * p) time, which degrades to O(n²) in the worst case. The optimized version uses the bisect module to achieve O(n log p) for the distribution phase.

Below is a complete, production-quality implementation that includes both phases and handles edge cases such as empty inputs, duplicate values, and stability. The code is heavily commented to clarify the role of each step and the invariants being maintained.

import bisect
import heapq

def patience_sort(arr):
    """
    Full patience sort that returns a new sorted list.
    Stable version: uses bisect_left to maintain stability.
    """
    if not arr:
        return []

    # Phase 1: Distribute into piles
    piles = []  # list of lists, each pile is a stack (top is last element)
    for card in arr:
        # Extract current pile tops for binary search
        tops = [pile[-1] for pile in piles]
        # Find leftmost pile with top >= card
        # bisect_left ensures stability for equal elements
        idx = bisect.bisect_left(tops, card)
        if idx == len(piles):
            piles.append([card])
        else:
            piles[idx].append(card)

    # Phase 2: K-way merge using a min-heap
    # Heap stores tuples of (value, pile_index, element_index)
    heap = []
    for i, pile in enumerate(piles):
        # pile is decreasing, so smallest is at the end
        # We need to merge from smallest to largest, so we pop from end
        # To make heap work, we reverse the pile conceptually
        # Actually piles are built with decreasing order, top is smallest in pile
        # So we start with the last element of each pile
        heapq.heappush(heap, (pile[-1], i, len(pile) - 1))

    result = []
    while heap:
        val, pile_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        # If there are more elements in this pile, push the next one
        if elem_idx > 0:
            next_val = piles[pile_idx][elem_idx - 1]
            heapq.heappush(heap, (next_val, pile_idx, elem_idx - 1))
    return result

# Example usage
data = [4, 3, 5, 1, 2, 6, 0]
print(patience_sort(data))  # [0, 1, 2, 3, 4, 5, 6]

The implementation above is stable because we use bisect_left. If we used bisect_right, equal elements would be placed on new piles to the right, which would reverse their original order during the merge. Stability is often required when sorting records with satellite data.

import bisect

def patience_sort_lis_length(arr):
    """
    Optimized patience sort for LIS length only.
    Returns length of Longest Increasing Subsequence.
    This is the classic O(n log n) LIS algorithm.
    Space: O(k) where k is LIS length.
    """
    if not arr:
        return 0
    
    # tails[i] = smallest possible tail value for an increasing
    # subsequence of length i+1
    tails = []
    for x in arr:
        # Find position to replace
        idx = bisect.bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
        # tails remains sorted, invariant maintained
    return len(tails)

def patience_sort_lis_sequence(arr):
    """
    Reconstructs one Longest Increasing Subsequence.
    Uses predecessor pointers and pile indices.
    """
    if not arr:
        return []
    
    n = len(arr)
    piles_tops = []  # values of pile tops
    # For reconstruction, we need to track piles and predecessors
    piles = []  # store indices
    predecessors = [-1] * n
    pile_indices = [-1] * n

    for i, x in enumerate(arr):
        idx = bisect.bisect_left(piles_tops, x)
        if idx == len(piles_tops):
            piles_tops.append(x)
            piles.append([i])
        else:
            piles_tops[idx] = x
            piles[idx].append(i)
        
        pile_indices[i] = idx
        if idx > 0:
            # Find predecessor: last element in previous pile with value < x
            # and index < i
            # For simplicity, we scan previous pile from end
            for j in reversed(piles[idx - 1]):
                if j < i and arr[j] < x:
                    predecessors[i] = j
                    break
    
    # Reconstruct LIS by backtracking from last pile
    lis = []
    if piles:
        curr = piles[-1][-1]
        # Find the actual end of LIS (may need to find max chain)
        # Simplified: backtrack from last element added to last pile
        while curr != -1:
            lis.append(arr[curr])
            curr = predecessors[curr]
        lis.reverse()
    return lis

print(patience_sort_lis_length([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(patience_sort_lis_sequence([10, 9, 2, 5, 3, 7, 101, 18]))

import bisect
import heapq

def patience_sort_optimized(arr, reverse=False):
    """
    Optimized variant with explicit handling of reverse sorting
    and early exit for already sorted data.
    """
    if not arr or len(arr) <= 1:
        return arr[:]

    # Early check for already sorted (common optimization)
    is_sorted = True
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            is_sorted = False
            break
    if is_sorted and not reverse:
        return arr[:]

    piles = []
    tops = []  # cache tops to avoid recomputing each time

    for card in arr:
        # Use bisect on cached tops
        idx = bisect.bisect_left(tops, card)
        if idx == len(piles):
            piles.append([card])
            tops.append(card)
        else:
            piles[idx].append(card)
            tops[idx] = card  # update top

    # If reverse requested, we can merge in descending order
    # by using a max-heap (negate values)
    heap = []
    for i, pile in enumerate(piles):
        heapq.heappush(heap, (pile[-1], i, len(pile) - 1))

    result = []
    while heap:
        val, pi, ei = heapq.heappop(heap)
        result.append(val)
        if ei > 0:
            heapq.heappush(heap, (piles[pi][ei - 1], pi, ei - 1))
    
    if reverse:
        result.reverse()
    return result

def patience_sort_with_stats(arr):
    """
    Instrumented version that returns sorting stats.
    Useful for analysis and visualization.
    """
    import bisect
    import heapq

    piles = []
    comparisons = 0
    for card in arr:
        tops = [p[-1] for p in piles]
        # Manual binary search to count comparisons
        lo, hi = 0, len(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            comparisons += 1
            if tops[mid] >= card:
                hi = mid
            else:
                lo = mid + 1
        if lo == len(piles):
            piles.append([card])
        else:
            piles[lo].append(card)

    num_piles = len(piles)
    max_pile_height = max(len(p) for p in piles) if piles else 0
    
    # Merge
    heap = [(p[-1], i, len(p)-1) for i, p in enumerate(piles)]
    heapq.heapify(heap)
    result = []
    while heap:
        v, pi, ei = heapq.heappop(heap)
        result.append(v)
        if ei > 0:
            heapq.heappush(heap, (piles[pi][ei-1], pi, ei-1))

    return {
        "sorted": result,
        "num_piles": num_piles,
        "max_pile_height": max_pile_height,
        "comparisons": comparisons,
        "piles": piles
    }

stats = patience_sort_with_stats([5, 1, 6, 2, 4, 3, 9, 8, 7])
print(f"Piles: {stats['piles']}")
print(f"Num piles: {stats['num_piles']}, Comparisons: {stats['comparisons']}")

4. Step-by-Step Example

To make the abstract mechanism concrete, let us walk through patience sort on the array [4, 1, 6, 2, 5, 3]. We will track the piles after each card is processed, showing how the greedy leftmost placement strategy works and how the final merge produces a sorted result.

We start with no piles. The first card is 4. Since there are no piles, we create Pile 1: [4]. The second card is 1. We compare 1 against the top of Pile 1, which is 4. Since 1 <= 4, we can place 1 on Pile 1. Pile 1 becomes [4, 1] where 1 is on top. Notice that the pile remains decreasing from bottom to top.

The third card is 6. The current pile tops are [1]. There is no pile with top >= 6, so we must create a new pile to the right. Piles are now: Pile 1: [4, 1], Pile 2: [6]. The tops are [1, 6], which are sorted increasingly. The fourth card is 2. We binary search the tops [1, 6] for the leftmost top >= 2. That is 6 at Pile 2. So we place 2 on Pile 2. Piles become: Pile 1: [4, 1], Pile 2: [6, 2]. Tops are now [1, 2].

The fifth card is 5. Tops are [1, 2]. No top is >= 5, so we create Pile 3: [5]. Piles: [4,1], [6,2], [5]. Tops: [1,2,5]. The final card is 3. Tops are [1,2,5]. The leftmost top >= 3 is 5 at Pile 3. We place 3 on Pile 3. Final piles: Pile 1: [4, 1], Pile 2: [6, 2], Pile 3: [5, 3]. Tops: [1, 2, 3]. The number of piles is 3, which tells us the length of the longest decreasing subsequence is 3 (for example, 4, 2 is not, but 6,5,3 or 4,2 is length 2, actually 6,5,3 is decreasing of length 3).

Now Phase 2 begins. We have three piles, each decreasing. To merge, we look at the tops: 1, 2, 3. The smallest is 1 from Pile 1. We output 1 and expose 4 underneath. Heap now contains 4, 2, 3. The smallest is 2 from Pile 2, output 2, expose 6. Heap: 4, 6, 3. Smallest is 3 from Pile 3, output 3, expose 5. Heap: 4, 6, 5. Smallest is 4, output 4, Pile 1 empty. Heap: 6, 5. Smallest is 5, output 5, Pile 3 empty. Heap: 6. Output 6. Final sorted array: [1, 2, 3, 4, 5, 6]. This walkthrough demonstrates how the algorithm never needs to compare elements within the same pile during the merge; it only ever compares pile tops.

Visual Trace Table

The following trace summarizes the state after each insertion. This is the exact information the instrumented code in the previous section would produce.

5. Complexity Analysis

Analyzing patience sort requires separating the two phases, as they have different cost drivers. The overall complexity is dominated by whichever phase is more expensive for a given input distribution. Understanding this nuance is key to knowing when patience sort is advantageous.

In Phase 1, each of the n elements requires a binary search over at most p pile tops, where p is the number of piles created. In the worst case, p can be n (when the input is strictly decreasing, each card needs a new pile), so the worst-case time for Phase 1 is O(n log n). In the best case where the input is already sorted increasingly, p = 1, and each binary search is O(log 1) = O(1), so Phase 1 is O(n). On average for random permutations, p is approximately O(sqrt(n)), leading to O(n log sqrt(n)) = O(n log n) but with a smaller constant than full comparison sorts.

Phase 2 is a k-way merge of p piles containing n elements total. Using a binary heap, each of the n extractions and insertions costs O(log p), so Phase 2 is O(n log p). In the worst case p = n, this is O(n log n). In the best case p = 1, it is O(n log 1) = O(n) if implemented to detect the single-pile case, otherwise O(n log n) with heap overhead. An important optimization is to detect p = 1 and simply reverse the single pile in O(n) time, since the pile is already decreasing and reversing it yields sorted order.

Space complexity is O(n) in all cases because we must store all n elements in piles. However, if only the LIS length is needed, space drops to O(p) = O(n) worst case but typically O(sqrt(n)). For full sorting, auxiliary space for the heap is O(p). The algorithm is not in-place; it requires O(n) additional storage for the piles and heap, which is a disadvantage compared to in-place algorithms like heapsort or quicksort when memory is constrained.

A subtle point is that patience sort's best-case O(n) time is achievable only with the single-pile optimization. Without it, even a sorted input would incur O(n log n) heap overhead. This is why practical implementations always check if the number of piles is small before choosing a merge strategy. For p < 64, a simple linear scan for the minimum top may even be faster than a heap due to cache locality and constant factors.

6. Variations and Optimizations

Several variations of patience sort have been developed to improve its practical performance and adapt it to different computational models. The most common optimization is to replace the heap-based merge with a more efficient merging strategy when the number of piles is small or when the data has specific characteristics.

One powerful variation is to use a tournament tree or loser tree instead of a binary heap for the k-way merge. While both have O(log p) per operation, tournament trees have better cache performance and fewer comparisons in practice because they avoid the heap's percolation overhead. For external sorting where piles are stored on disk, a multiway merge with a large fan-in is essential, and patience sort's naturally created runs are often longer than those created by simple replacement selection.

Another optimization concerns the binary search in Phase 1. Since pile tops are sorted, we can use bisect from Python's standard library, which is implemented in C and extremely fast. For very large p, interpolation search or exponential search can be considered if the pile tops are uniformly distributed, though binary search is optimal in the worst case. Additionally, caching the list of tops separately from the piles avoids reconstructing it on every iteration, as shown in the optimized implementation above.

Adaptive and Stable Variants

Patience sort is naturally adaptive: it performs better on partially sorted inputs. This adaptivity can be enhanced by allowing a pile to accept a card if it is greater than or equal to the top, versus strictly greater. Using >= (bisect_left) creates fewer piles for inputs with many duplicates and preserves stability, while using > (bisect_right) creates more piles but can be useful when strict increasing order is required for LIS. The choice affects both the number of piles and the stability guarantee.

A hybrid approach combines patience sort with insertion sort for small piles. When piles are very short, the overhead of heap management dominates. In this case, after Phase 1, one can simply concatenate the piles and run insertion sort, or use a simple linear scan to find the minimum top instead of a heap. For p < 10, linear scan is often faster due to branch prediction and cache effects.

Finally, there is a parallel variant. Phase 1 is inherently sequential because the placement of each card depends on all previous placements. However, Phase 2's k-way merge can be parallelized using parallel heap or by merging piles pairwise in parallel, similar to parallel merge sort. In distributed systems, each node can perform patience sort locally to create sorted runs, which are then merged globally, leveraging the algorithm's ability to create long runs from partially ordered data.

7. Real-World Applications

While you will rarely find patience sort as the default sort in a general-purpose library, its principles and its LIS variant are pervasive in real systems. Its value often lies not in sorting an entire array from scratch, but in efficiently handling data that is already partially structured or in solving related subsequence problems.

In bioinformatics, patience sort's LIS algorithm is used for genome sequence alignment and for finding the longest common subsequence between DNA strings. When comparing two genetic sequences, the problem of finding conserved regions reduces to finding an increasing subsequence of matches. The O(n log n) patience sort method is the standard solution for the LIS step in many alignment tools, where n can be millions of base pairs and an O(n²) dynamic programming solution would be infeasible.

In networking and databases, patience sort is relevant to problems involving out-of-order packet reassembly and log merging. Web servers and distributed databases often receive events with timestamps that are mostly ordered but may have some disorder due to clock skew or network delays. Patience sort's pile structure efficiently identifies the longest ordered subsequence and can be used to buffer and reorder streams with minimal pile count, which corresponds to minimal buffer memory. Similarly, in external sorting for databases, the concept of creating initial sorted runs (like patience piles) before merging is fundamental; replacement selection, used in database sort-merge joins, is a direct descendant of this idea.

Version control systems and diff utilities, such as those powering git diff and diff3, use patience diff, an algorithm directly based on patience sort. Traditional diff algorithms based on longest common subsequence can produce confusing diffs when code blocks are reordered. Patience diff first finds unique lines that appear exactly once in both files, uses patience sort to find the longest increasing subsequence of those unique matches to anchor the diff, and then recursively diffs the regions between anchors. This produces more human-readable diffs, especially for source code where functions may be moved.

In air traffic control and scheduling, patience sort models the problem of partitioning a set of intervals into the minimum number of resources. For example, assigning arriving flights to runways or scheduling tasks to machines such that no machine processes overlapping tasks is equivalent to partitioning a permutation into decreasing subsequences, which patience sort does optimally. The number of piles is the minimum number of runways or machines needed.

8. Comparison with Alternatives

Choosing a sorting algorithm requires weighing time complexity, space usage, stability, adaptivity, and implementation simplicity. Patience sort occupies a unique niche: it is not the fastest general-purpose sort, but it is optimal for specific data distributions and provides extra structural information that other sorts do not.

Compared to classic O(n log n) sorts like merge sort and heapsort, patience sort has the same asymptotic worst-case time but higher constant factors due to heap overhead and non-in-place operation. However, unlike heapsort, it is stable and adaptive. Compared to quicksort, it avoids quicksort's O(n²) worst case and is stable, but quicksort is typically faster in practice for random data due to excellent cache locality and in-place partitioning. Timsort, Python's own sorting algorithm, actually incorporates ideas similar to patience sort: it identifies naturally occurring runs (like piles) and merges them, which is why Timsort is so effective on real-world partially sorted data.

For the specific task of finding the longest increasing subsequence, patience sort's O(n log n) method is strictly superior to the classic O(n²) dynamic programming approach for n > 100. The DP method is simpler to understand and can reconstruct the actual subsequence more easily without predecessor pointers, but it does not scale. For full sorting of small arrays, insertion sort will beat patience sort due to lower overhead, which is why many hybrid sorts use insertion sort for subarrays smaller than ~32 elements.

In summary, use patience sort when you need LIS information, when your data has long increasing runs, or when you are implementing an external sort where run generation matters. Use merge sort or Timsort for stable general-purpose sorting, quicksort when average speed and in-place operation are paramount, and insertion sort for tiny or nearly sorted arrays. In practice, the best systems combine these ideas, as Timsort does by merging runs discovered via a patience-like scan.

9. Common Mistakes and Best Practices

Implementing patience sort correctly requires attention to several subtle details that are easy to overlook. The most frequent mistake is using a linear scan to find the correct pile instead of binary search. While a linear scan is correct, it degrades Phase 1 to O(n * p) = O(n²) in the worst case, completely negating the algorithm's O(n log n) guarantee. Always maintain the invariant that pile tops are sorted and use bisect_left or a manual binary search.

A second common pitfall is mishandling duplicates and stability. If you use bisect_right (placing equal cards on a new pile to the right) when you need a stable sort, equal elements will appear in reverse order after merging. For a stable sort, you must use bisect_left so that equal elements are stacked on the same pile, preserving their original relative order when piles are merged. Conversely, if you are computing the strictly increasing LIS, you should use bisect_left to replace equal values, while for non-decreasing LIS you use bisect_right. Confusing these two cases leads to off-by-one errors in LIS length.

Another mistake is inefficient merging. A naive merge that repeatedly scans all pile tops linearly to find the minimum results in O(n * p) time for Phase 2. Always use a heap or tournament tree for p > 10. Also, remember that each pile is stored with the smallest element on top (last element of the list). A frequent bug is to push the first element of the pile onto the heap instead of the last, which breaks the merge order. Be explicit about whether your pile's top is at index 0 or -1 and keep it consistent.

Best practices include caching pile tops, handling edge cases, and choosing the right variant for the job. Cache the tops array to avoid rebuilding it with a list comprehension on every iteration; update it in place when you place a card. Always handle empty input, single-element input, and inputs where all elements are equal. If you only need LIS length, do not store full piles; store only tops to save memory. Finally, profile before optimizing: for n < 1000, the overhead of heap and bisect may make patience sort slower than Python's built-in sorted(), which is implemented in highly optimized C.

10. Interview Questions

Patience sort is a favorite topic in technical interviews because it tests understanding of binary search, heaps, greedy algorithms, and the connection between sorting and subsequence problems. Interviewers rarely ask you to implement full patience sort from scratch, but they frequently probe the underlying concepts.

Q1: How can you find the length of the Longest Increasing Subsequence in O(n log n) time?

Answer: Use the patience sort pile-tops method. Maintain an array tails where tails[i] is the smallest possible tail value of an increasing subsequence of length i+1. For each x in the input, find the leftmost index i where tails[i] >= x using binary search (bisect_left). If i == len(tails), append x; otherwise replace tails[i] with x. The length of tails at the end is the LIS length. Explain why this works: replacing the tail keeps future possibilities open by maintaining the smallest achievable tail for each length, and the greedy choice is optimal due to the sorted invariant of tails.

Q2: What is the relationship between the number of piles in patience sort and the Longest Decreasing Subsequence?

Answer: The number of piles created by patience sort equals the length of the longest decreasing subsequence of the input. This is a direct consequence of Dilworth's theorem. Each pile is decreasing, so a decreasing subsequence can have at most one element from each pile, and by the pigeonhole principle, any partition into p decreasing piles implies a decreasing subsequence of length p. Conversely, patience sort constructs a minimal partition into decreasing piles, so p is exactly the optimum. Be prepared to prove this with an example and to explain how to modify the comparison (>= vs >) to get LIS vs LDS.

Q3: Why must you place each card on the leftmost eligible pile? What happens if you choose a different pile?

Answer: Choosing the leftmost eligible pile is the greedy choice that guarantees minimal number of piles and maintains the sorted order of pile tops, which enables binary search. If you place a card on a non-leftmost eligible pile, you may create more piles than necessary and break the invariant that tops are sorted. For example, with tops [1, 6] and card 2, placing 2 on a new pile instead of on 6 would create tops [1, 6, 2] which are not sorted, making future binary searches incorrect and increasing p unnecessarily. This demonstrates understanding of greedy correctness and invariants.

Q4: Compare patience sort's merge phase to merge sort's merge. When would you prefer one over the other?

Answer: Both perform a k-way merge, but merge sort's merge is always 2-way and operates on contiguous sorted subarrays, giving excellent cache locality and predictable O(n log n) performance. Patience sort's merge is p-way where p depends on input order; for sorted data p=1 (O(n)), for random data p ~ sqrt(n), for reverse sorted data p=n (O(n log n) with high overhead). Prefer patience sort when data has many presorted runs or when you need LIS information; prefer merge sort for general-purpose stable sorting with guaranteed performance and better locality. Mention that Timsort combines both ideas by detecting runs like patience sort and merging like merge sort.

Q5: How would you make patience sort stable and what is its space complexity?

Answer: To make it stable, use bisect_left (place card on leftmost pile with top >= card) so equal elements are stacked in order, and when merging, break heap ties by pile index or insertion order. The heap should store (value, pile_index, element_index) and heap order will then respect original order for equal values. Space complexity is O(n) for full sorting because all elements are stored in piles plus O(p) for the heap. For LIS length only, space is O(p) for tops. Emphasize that it is not in-place, unlike heapsort, and discuss the trade-off between extra space and adaptivity.