ペイシェンスソートを使用する

ペイシェンスソート (patience sort) は、ソリティアでトランプを並べていくときの規則に似せたアルゴリズムである。左から並ぶ複数の山（パイル）に入力を順に載せ、その後それらの一番上の値のみを読みながら昇順への取り出しを続けることで並び替えを完結させる構想になる。

  1. 積載: 入力配列を先頭から左へ見ていき、現在の値 x について、一番上の値が (x) より大きいなかで先頭にあるパイルを探し、その山の上へ x を載せる。

    該当する山がひとつもなければ、一番右に新しい山を増やしてそこに x だけ載せた状態から始める。

  2. 取出: すべての山が空になるまで、一番上の値のうち現在の最小値を持っている山ひとつを選び、その値を取り除いて結果列の末尾へ付ける。

    一番上の値だけを対象とするのでマージソートと同種のマージ処理の特殊形だと見なせる。

procedure patience_deal(elements)
  piles = sequence of piles, initially empty lists
  for each x in elements then
    i = smallest index where piles[i] is non-empty AND top(piles[i]) > x
           (otherwise i = undefined)
    if i is undefined then
      piles.append([x])
    else then
      push x onto piles[i]

procedure patience_collect(piles)
  result = []
  until all piles empty then
    p = pile index minimizing top(piles[p]), breaking ties arbitrarily
    y = pop top from piles[p]
    append y to result
  return result

山の総数によらず、一番上の値の参照にはヒープなどを使える。また積載のルールだけを切り離してみると、山の個数が増加部分列についてのモデルとも対応することが知られている。

同じ値が並んでいても、「一番上の値が載せたい値より厳密に大きい」という条件だけで載せる山が決まり、並べ替え前の順序まで保証しないため、安定ソートではない。また 入力とは別に山と出力領域 を要する。

アルゴリズムの名前は単純比較ベースとは別の発想になりやすいが、並び変え問題として見れば 入力をいくつかの単調並びに分解し、その後統合して完成させる という広い視点での仲間となる。