↩ back to Comparison Sorts

Patience Sort

Longest Increasing Subsequence's own O(n log n) method already builds this technique's core step — deal each value onto the leftmost pile whose current top is at least as large, binary-searching for that pile — but stops the moment it only needs pile count, the LIS length. That page even names the sorting game this is borrowed from without building it: "figuring out the minimum number of patience/solitaire piles a shuffled deck can be sorted into." Patience Sort keeps going. Once every value has been dealt, recover the full sorted array by repeatedly taking whichever pile's visible top card is currently smallest — a merge across as many piles as the deal produced, not the two-way merge merge sort repeats O(log n) times. Every other comparison sort on this site restructures one array in place or merges pre-built runs; this one is built from a real card game, where cards are dealt face-up onto piles you're only ever allowed to see the top of.

Try it

Enter a comma-separated array (up to 14 values, duplicates welcome) and step through two phases. Dealing: each card goes onto the leftmost pile whose current top is ≥ the card — found by binary search, which works because pile tops read left to right are always increasing — or starts a new pile at the right end if no pile qualifies. Merging: repeatedly compare every live pile's current top (the rightmost card in its row below — the only one this technique is allowed to look at) and send the smallest to the output. Piles are drawn as chained rows, the same shape this site's Bucket Sort demo uses for its own buckets — same shape, different meaning: a bucket's row is fixed by arithmetic before anything is ever compared, a pile's row is built by comparing only the one card currently visible.

Why it works

Placing a card only ever happens on a pile whose top is ≥ it, and the placed card becomes the pile's new top — so every pile, followed in the order its cards were dealt, is non-increasing: each new top is never bigger than the one before it. That's the whole invariant the merge phase leans on. It also means the whole collection of pile tops, read left to right across piles, stays non-decreasing after every single card: a new low top can only ever appear to the right of the pile it just undercut, never to its left. That second invariant is what makes binary search valid for finding "the leftmost pile with top ≥ card" in the first place — the exact search LIS's own page already runs, reused here verbatim, not reinvented.

Choosing the leftmost qualifying pile isn't what makes the merge below produce a correct sort — placing a card on any pile whose top is ≥ it would keep that pile's own non-increasing order intact just as well (checked directly: forcing strict > instead of ≥, which routes some duplicates onto different piles than the leftmost rule would, still produced a correct sort on every one of 20,000 random trials). Leftmost is what minimizes the number of piles — the property LIS's page actually needs, since that minimum pile count is the LIS length. Sorting only needs every pile internally consistent, not minimal.

Once dealing is done, every pile is individually sorted smallest-on-top. The card with the overall smallest value left anywhere has to be sitting on top of some pile — it can't be buried, because everything above it in its own pile is smaller still, and it isn't on any other pile at all. So comparing just the k visible tops and taking the smallest, repeated until every pile is empty, produces the cards in fully sorted order — the same "compare only the fronts" principle behind merging two sorted runs in merge sort, generalized from two runs to k.

Reference implementation

function patienceSort(input) {
  const piles = []; // each pile: cards in the order they were dealt; last = current top

  for (const card of input) {                     // deal
    let lo = 0, hi = piles.length;
    while (lo < hi) {                              // binary search: leftmost pile, top >= card
      const mid = (lo + hi) >> 1;
      const top = piles[mid][piles[mid].length - 1];
      if (top >= card) hi = mid; else lo = mid + 1;
    }
    if (lo === piles.length) piles.push([card]);   // no qualifying pile — start a new one
    else piles[lo].push(card);
  }

  const out = [];                                  // merge
  let remaining = input.length;
  while (remaining > 0) {
    let bestPile = -1, bestVal = Infinity;
    for (let i = 0; i < piles.length; i++) {
      if (piles[i].length === 0) continue;
      const top = piles[i][piles[i].length - 1];
      if (top < bestVal) { bestVal = top; bestPile = i; }
    }
    out.push(piles[bestPile].pop());
    remaining--;
  }
  return out;
}

The merge above finds the minimum top by scanning every live pile, the same "clarity over a heap you've already seen" choice Dijkstra's own reference implementation makes for its priority queue — see Pitfalls and Complexity below for exactly what that choice costs here.

Pitfalls

Confusing a pile's top with its bottom during the merge breaks the sort outright, not just the pile count. The natural version of this bug: model each pile as a plain array, deal by pushing (correct — new cards do belong on top), then merge by reading pile[0] and removing it with shift() instead of reading pile[pile.length - 1] and removing it with pop(). pile[0] is the first card ever dealt onto that pile — the oldest, and (by the invariant above) the largest value the pile holds, the exact opposite of what "top" means once cards stack. Minimal example: input [3, 1] deals both cards onto one pile (3 first, then 1 on top of it, since 3 ≥ 1). The correct merge pops 1 then 3, giving [1, 3]. The bottom-reading version returns [3, 1] — the original input, completely unsorted, no error thrown. Stress-tested directly (arrays length 2–26, values 0–11, 20,000 random trials): 16,155 of 20,000 (80.8%) came back wrong.

The linear scan for the merge minimum isn't just a constant-factor slowdown — it changes which inputs are fast, in the opposite direction from almost every other adaptive sort on this site. Total merge work is O(n·k), where k is however many piles the deal phase produced, and k is entirely data-dependent. An already ascending array is the worst case for k: no card ever qualifies for an existing pile (every top is smaller than the next card), so every card starts its own pile and k = n — measured at n = 1,000: 1,000 piles, 500,500 merge comparisons (exactly n(n+1)/2), real O(n²). An already descending array is the opposite extreme: every card qualifies for the one pile that already exists, so k = 1 — measured at the same n = 1,000: 1 pile, 1,000 merge comparisons, real O(n). Random input lands between the two (measured, n = 1,000, averaged over 20 trials): about 57 piles, 52,200 merge comparisons. Insertion sort, bubble sort, and Timsort all treat already-ascending input as their easy case; this page's merge treats it as its hardest. The deal phase's own binary search stays cheap regardless of order — 7,987 comparisons ascending, 999 descending, both close to O(n log k) — the blowup above is entirely the merge's linear scan, not the deal. A min-heap over the k pile tops (this site's own heap entry) would bring the merge down to O(n log k) in every case, matching the guarantee Dijkstra's own named same tradeoff makes for exactly the same reason.

Complexity

Time: deal phase O(n log k) always, where k is the final pile count — one binary search per card over however many piles exist so far, confirmed data-independent above. Merge phase O(n·k) for this page's linear-scan implementation — O(n) when k is small (measured on descending input), O(n²) when k = Θ(n) (measured on ascending input, the worst case for this technique specifically). k itself is exactly the length of the longest non-decreasing run structure LIS's own page computes with the same binary search — worst case k = n (fully ascending input, ironically), best case k = 1 (fully descending). Space: O(n) — every card is held in exactly one pile at all times, plus the output array. Stable: no — checked directly (duplicate-heavy tagged arrays, 2,000 trials): 1,987 of 2,000 (99.4%) came back with at least one equal-valued pair out of its original relative order, since which pile a duplicate lands on (and therefore which order ties leave the merge in) depends on the whole deal history, not just the two tied values.

See Choosing a Comparison Sort for how this fits against the other eleven Comparison Sorts entries — short version: not a candidate for the small-n/stability/worst-case-guarantee funnel any more than Bitonic Sort or Cycle Sort are, but for yet another reason than either of those two — it's the one entry built from a genuinely different structure (piles you can only see the top of) instead of restructuring one array in place, and the one whose easy and hard cases run backward from every adaptive sort around it.