How does the patience sort algorithm work?

Patience Sort is an algorithm that sorts a sequence by creating piles of cards and merging them in ascending order.

Patience Sort is a card game-inspired sorting algorithm that is based on the game of Patience (also known as Solitaire). The algorithm begins by dealing cards onto piles following specific rules. Each card from the input sequence is placed on the leftmost pile where it can go on top of the current top card of that pile. If there is no such pile, a new pile is created to the right of all existing piles. The card is always placed on top of the smaller card, and if there is no smaller card, it starts a new pile.

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

Once all the cards have been dealt into piles, the algorithm proceeds to the second phase: merging the piles. This is done by repeatedly picking the smallest visible card and moving it to the output sequence. This is similar to the merge step in a merge sort, and can be done efficiently using a priority queue. The piles are merged together in ascending order until there are no more cards left.

The Patience Sort algorithm is not used as much in practice as other sorting algorithms like Quick Sort or Merge Sort, because it has a worst-case time complexity of O(n^2). However, it has interesting theoretical properties and is useful in certain niche applications. For example, it can be used to find the longest increasing subsequence of a sequence in O(n log n) time.