Patience Sort is a sorting algorithm that organizes a sequence by creating and merging piles of cards in ascending order.

Inspired by the card game Patience (also known as Solitaire), Patience Sort operates by dealing cards into piles according to specific rules. Each card from the input sequence is placed on the leftmost pile where it can be positioned atop the current top card of that pile. If no existing pile can accommodate the card, a new pile is created to the right of all current piles. Cards are always placed on top of a smaller card, and if no smaller card exists, a new pile is initiated.

The piles are arranged in increasing order from left to right, with the smallest card located on the leftmost pile and the largest card on the rightmost pile. It is important to note that the piles themselves are not sorted; only the top card of each pile is significant. The total number of piles corresponds to the length of the longest increasing subsequence in the input sequence.

After all the cards have been distributed into piles, the algorithm advances to the second phase: merging the piles. This process involves repeatedly selecting the smallest visible card and placing it into the output sequence, akin to the merging step in a merge sort. This merging can be performed efficiently using a priority queue. The piles are combined in ascending order until no cards remain.

Although Patience Sort is less commonly used in practice compared to other sorting algorithms like Quick Sort or Merge Sort due to its worst-case time complexity of $O(n^2)$, it possesses intriguing theoretical properties and finds utility in certain niche applications. Notably, it can be employed to determine the longest increasing subsequence of a sequence in $O(n \log n)$ time.