# Patience Sort with Piles

# Patience Sort with Piles

Patience sort with piles is the full sorting version of patience sorting. It builds piles using the same rule as the LIS method, then merges the piles to produce a sorted sequence.

You use it when you want a conceptually simple sorting method based on binary search and merging.

## Problem

Given an array ( A ), sort it by:

1. building piles using patience sorting rules
2. merging those piles

## Idea

Each pile is kept in increasing order from bottom to top. Pile tops are sorted, which allows binary search to find the correct pile for each element.

After all elements are processed, piles are merged like in multiway merge.

## Algorithm

### Phase 1: Build piles

```id="p1a9k3"
build_piles(A):
    piles = []

    for x in A:
        i = lower_bound(pile_tops(piles), x)

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

    return piles
```

### Phase 2: Merge piles

```id="r3m8t2"
merge_piles(piles):
    heap = []

    for i in 0..length(piles)-1:
        push(heap, (top(piles[i]), i))

    result = []

    while heap not empty:
        (value, i) = pop(heap)
        result.append(value)
        remove_top(piles[i])

        if piles[i] not empty:
            push(heap, (top(piles[i]), i))

    return result
```

## Example

Input:

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

Pile construction:

| step |  x | piles (tops) |
| ---- | -: | ------------ |
| 1    |  4 | [4]          |
| 2    |  3 | [3]          |
| 3    |  5 | [3, 5]       |
| 4    |  1 | [1, 5]       |
| 5    |  2 | [1, 2]       |

Piles (full):

* pile 1: [4, 3, 1]
* pile 2: [5, 2]

Merge produces:

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

## Correctness

Pile construction ensures:

* pile tops are sorted
* each pile is internally ordered

The merge step extracts the smallest available top across all piles. This is equivalent to merging sorted sequences, so the result is sorted.

## Complexity

| phase       | cost                         |
| ----------- | ---------------------------- |
| build piles | ( O(n \log n) )              |
| merge piles | ( O(n \log p) ), ( p \le n ) |

Total:

[
O(n \log n)
]

Space:

[
O(n)
]

## Relation to LIS

The number of piles equals the length of the longest increasing subsequence. This connects sorting behavior with sequence structure.

## When to Use

Patience sort with piles is useful when:

* you want a clear conceptual algorithm
* LIS structure is relevant
* multiway merging is acceptable

In practice, it is less efficient than optimized merge or quicksort variants, but valuable for understanding adaptive sorting and sequence properties.