Interactive demo
Patience Sort Visualization
Patience sort is named after the card game patience (solitaire). Every card goes on the leftmost pile whose top card is larger. Then the smallest top card is collected, again and again, until all piles are empty.
Choose “Reversed”: everything lands on a single pile. With “Sorted” every card starts a pile of its own.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element in the array
- Card being dealt
- Card on a pile
- Final position
Runtime and properties
Best case
O(n)
Reversed input forms a single pile that is simply taken off from the top.
Average case
O(n log n)
Binary searches over the piles, then a priority queue of the tops: log n steps per element.
Worst case
O(n log n)
Even with n piles, each element needs only log n comparisons with a priority queue.
Extra memory
O(n)
Every element lies on a pile outside the array.
Stable
Yes
Here equal elements never lie on each other, and ties are taken from the left pile.
In-place
No
The piles are built outside the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort this page | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Deal the piles
Every card goes on the leftmost pile whose top card is larger; if there is none, it starts a new pile on the right. The top cards then always stay sorted from left to right, so a binary search finds the right pile.
2. Collect
Every pile is sorted from the top down. The smallest of all top cards is therefore the next element of the sorted array. Here the top cards are compared one by one; efficient versions keep them in a priority queue (a heap) for log n comparisons per element.
3. Longest increasing subsequence
The number of piles equals the length of the longest increasing subsequence of the input. That is why the dealing phase is also used on its own, for example to compare versions of text files.