# Patience Sort

# 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

```id="k3x9p1"
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

```id="m2x8q4"
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
```

```id="z6k3v2"
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
}
```