デカルト木ソートを使用する

デカルト木ソート (cartesian tree sort) は、配列から デカルト木 (Cartesian tree) を一度だけ構築し、根（部分木の最小値）を先頭に取り出しつつ左右部分木の結果を マージ (merge) して昇順の並びを得る整列である。

デカルト木は次の2条件を同時に満たす二分木である。

  1. 中順が元の配列順: 左部分木 → 根 → 右部分木の順に走査すると、元の配列の左から右への並び（添字の昇順）になる。
  2. ヒープ性: 最小デカルト木では、各親の値は両方の子以下である（最大デカルト木では逆）。

入力配列が決まれば、値がすべて異なるときデカルト木の形は一意に定まる。整列では最小デカルト木を想定する。

素朴に「根を選んで再帰的に部分木を作る」と O(n²) になりうるが、単調スタック (monotonic stack) を使えば各添字はスタックに 高々1回入り1回出る ため、全体で O(n) 時間に木を構築できる。

添字 i を左から処理するときの典型形は次のとおりである。

  1. スタック上端より大きい値の添字を、値が A[i] 以下になるまで pop する（最後に pop した添字を last とする）。
  2. スタックが空でなければ、A[i] はスタック上端の 右の子 になる。
  3. last があれば、その添字は i の 左の子 になる。
  4. i をスタックに push する。
procedure build_cartesian_tree(A)
  stack = empty stack of indices
  for i from 0 to length(A) - 1
    last = null
    while stack not empty and A[stack.top] > A[i]
      last = stack.pop()
    if stack not empty
      right[stack.top] = i
    if last not null
      left[i] = last
    stack.push(i)
  return tree encoded by left[], right[], and stack[0] as root

構築後、各ノードについて根のキーを出力し、左右部分木から得た すでに昇順の列 をマージする再帰的取出しで整列する。左右部分木は元配列の連続部分区間に対応するため、再帰の各段階で部分列は昇順に保たれる。

procedure merge(L, R)
  // 2 つの昇順列を先頭から比較しながら連結する

procedure extract_sorted(node)
  if node is null
    return empty list
  left = extract_sorted(left[node])
  right = extract_sorted(right[node])
  return [A[node]] followed by merge(left, right)

素朴なマージを重ねると O(n log n) 時間になるが、スタック構築と組み合わせた技法では O(n) まで落とせる（ここでは取出しの意味論だけ示す）。

比較ソートの Ω(n log n) 下界 とは一見矛盾するように見えるが、デカルト木は「値の大小」だけでなく 元配列の添字順（中順が元の並びになる制約） も構造に使う。位置情報付きの入力に対する 線形時間の木構築 であり、比較だけで順序を決め打ちする一般の比較ソートモデルとは前提が異なる。

安定性は等値キーの左右の付け方に依存し、一般的な実装ではスタック上の添字の順序で決まるため、不安定 である。

クイックソートの分割木や、二分木ソートの「挿入順で形が変わる木」とも対比しやすい。範囲最小クエリ (RMQ) や最長増加部分列 (LIS) など、同じスタック構造が別問題でも登場する。

以下のデモでは、同値の棒が入れ替わらないよう、ヒープ比較を 値が異なれば値、等しければ元の位置 id の辞書式順にしている（可視化上の安定化であり、一般のデカルト木ソートの性質を変えるものではない）。

  1. 構築: 左から添字を処理し、スタックとの比較（オレンジ）とリンク付け（紫）を示す。木自体は内部データとして保持する。
  2. 取出し: 根優先の再帰取出し＋マージで得た昇順に、配列上の棒を スワップ（緑） で並べ替えて視覚化する（実装では取出し結果を別バッファへ書くだけでよい）。

二分木ソートのように 平衡木への挿入 を繰り返すのではなく、配列と添字順から 一度で デカルト木が定まる点が特徴である。