Patience Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Patience Sort

A card-game inspired sorting algorithm: distributes elements onto a series of piles such that each pile's top is \(\ge\) the incoming value, then performs a multi-way merge across pile tops.

How it works

Patience Sort is inspired by the Patience card game (Solitaire) and was analyzed by C.L. Mallows in 1962. It is highly valued in mathematics because it relates directly to finding the **Longest Increasing Subsequence (LIS)** in an array. The sorting algorithm follows two distinct phases:

1. **Pile Distribution:** Scan the array from left to right. For each element:
   • Find the first pile (from left to right) whose top element is greater than or equal to the current element. Place the element on top of that pile.
   • If no such pile exists, create a new pile to the right of all existing piles and place the element on it.
   • This ensures that inside each pile, elements are sorted in descending order from bottom to top, and the top elements of the piles form an ascending sequence from left to right.
2. **Multi-way Merge:**
   • To reconstruct the sorted list, repeatedly extract the minimum top element across all active piles and append it to the sorted output.
   • This is a standard multi-way merge of sorted piles.

Complexity

Interactive visualization

Pseudocode

procedure patienceSort(A):
  piles ← empty list of piles
  
  # Phase 1: Distribute elements to piles
  for each val in A:
    pileIdx ← binarySearchPiles(piles, val)
    if pileIdx < length(piles):
      piles[pileIdx].push(val)
    else:
      piles.push([val])
      
  # Phase 2: Merge piles
  for i from 0 to length(A) - 1:
    A[i] ← popMinTopCard(piles)

JavaScript implementation

function patienceSort(arr) {
  const piles = [];
  
  // 1. Distribute onto piles
  for (let i = 0; i < arr.length; i++) {
    const val = arr[i];
    let low = 0, high = piles.length;
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      const top = piles[mid][piles[mid].length - 1];
      if (top >= val) high = mid;
      else low = mid + 1;
    }
    
    if (low < piles.length) {
      piles[low].push(val);
    } else {
      piles.push([val]);
    }
  }
  
  // 2. Merge piles
  for (let i = 0; i < arr.length; i++) {
    let minVal = Infinity;
    let minPileIdx = -1;
    for (let p = 0; p < piles.length; p++) {
      if (piles[p].length > 0) {
        const top = piles[p][piles[p].length - 1];
        if (top < minVal) {
          minVal = top;
          minPileIdx = p;
        }
      }
    }
    arr[i] = minVal;
    piles[minPileIdx].pop();
  }
  return arr;
}

Pros and cons

When (not) to use it

• LIS Calculation: The absolute standard algorithm for finding the LIS in sub-quadratic time.
• Standard Arrays: Avoid; standard internal comparison sorts like Heapsort or Quicksort do not suffer from the stack/list allocation overhead of piles.