Patience Sort

Patience sort builds a set of piles using rules similar to the patience card game. Each element is placed on the leftmost pile whose top element is greater than or equal to it. After all elements are distributed into piles, the piles are merged to produce a sorted sequence.

This algorithm is closely related to the longest increasing subsequence problem.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Key Idea

Maintain piles where each pile is sorted in decreasing order from bottom to top
Use binary search over pile tops to find where to place each element
Merge piles to obtain the final sorted sequence

Algorithm

patience_sort(A):
    piles = empty list

    for x in A:
        find leftmost pile whose top >= x
        if such pile exists:
            place x on top of that pile
        else:
            create new pile with x

    return merge_all_piles(piles)

Example

Let

A = [4, 3, 5, 1, 2]

Build piles:

Step 1: [4] Step 2: [4], [3] Step 3: [4], [3], [5] Step 4: [1], [3], [5] Step 5: [1], [2], [5]

Piles (top elements increasing):

[1], [2], [5]

Merging piles produces:

[1, 2, 3, 4, 5]

Correctness

Each pile maintains decreasing order, and pile tops are in increasing order from left to right. This structure ensures that merging the piles yields a globally sorted sequence.

The pile construction also reflects the structure of increasing subsequences in the input.

Complexity

phase	time
pile building	$O(n \log n)$
merging	$O(n \log n)$

Total time:

O(n \log n)

Space complexity:

O(n)

Properties

not in-place
not stable in basic form
uses binary search
closely related to LIS algorithms

When to Use

Patience sort is useful for understanding the structure of sequences and their subsequences. It is often used in theoretical contexts and in algorithms for computing the longest increasing subsequence.

Implementation

import heapq
from bisect import bisect_left

def patience_sort(a):
    piles = []

    for x in a:
        tops = [pile[-1] for pile in piles]
        i = bisect_left(tops, x)

        if i == len(piles):
            piles.append([x])
        else:
            piles[i].append(x)

    heap = []
    for i, pile in enumerate(piles):
        heapq.heappush(heap, (pile.pop(), i))

    result = []
    while heap:
        value, i = heapq.heappop(heap)
        result.append(value)
        if piles[i]:
            heapq.heappush(heap, (piles[i].pop(), i))

    return result

func PatienceSort(a []int) []int {
    var piles [][]int

    for _, x := range a {
        i := 0
        for i < len(piles) && piles[i][len(piles[i])-1] < x {
            i++
        }

        if i == len(piles) {
            piles = append(piles, []int{x})
        } else {
            piles[i] = append(piles[i], x)
        }
    }

    result := []int{}
    indices := make([]int, len(piles))

    for {
        minVal := int(^uint(0) >> 1)
        minIdx := -1

        for i := range piles {
            if indices[i] < len(piles[i]) {
                v := piles[i][len(piles[i])-1-indices[i]]
                if v < minVal {
                    minVal = v
                    minIdx = i
                }
            }
        }

        if minIdx == -1 {
            break
        }

        result = append(result, minVal)
        indices[minIdx]++
    }

    return result
}