Summary

Patience Sort is a two-phase algorithm named after the Patience card game. In the first phase, elements are distributed into piles. A new element is placed on the leftmost pile where the top card is greater than or equal to the new element. If no such pile exists, a new pile is started. This process incidentally calculates the length of the Longest Increasing Subsequence (which equals the number of piles). In the second phase, the algorithm performs a $k$-way merge of the piles using a Min-Heap to reconstruct the sorted sequence.

How it Works

• Phase 1: Piling: Iterate through the input array one element at a time.

• For each element $x$, perform a binary search on the "top" cards of the existing piles to find the leftmost pile where $top \ge x$.

• If such a pile is found, place $x$ on top of it. If not, create a new pile with $x$ as the first card.

• Phase 2: Merging: Once all elements are in piles, initialize a Min-Heap with the top card from every pile.

• Repeatedly extract the minimum value from the heap and add it to the sorted output array.

• When a card is removed from a pile, if the pile is not empty, push the next card from that pile into the heap.

• Repeat until all piles are empty.