二分木ソートを使用する

二分木ソート (tree sort) は、要素を順に 二分探索木 (binary search tree) へ挿入し、その後中順走査 (in-order traversal; 左部分木 → 根 → 右部分木) ですべてのキーを読み出して昇順を得る比較ソートである。

通常の二分探索木は挿入順によって木の高さが偏りやすく、特定の入力では高さが O(n) になり、結果として時間計算量が O(n²) に悪化する。

そこで 平衡二分探索木 (self-balancing binary search tree)を使うと、木の高さを O(log n) に抑えられる。

平衡木への各挿入は高さ O(log n) の探索と再平衡化を伴うため、挿入全体で O(n log n) となる。一方、中順走査は左部分木、根、右部分木の順に各ノードを一度ずつ処理するだけなので全体でO(n) である。

したがって、合計は O(n log n) + O(n) = O(n log n) となる。別途 木全体のために O(n) のノード記憶域が必要になり、入力配列とは別構造となる点はインプレースではない。

また、キー（ここでは棒の高さ＝値）だけで比較する素のツリーソートでは、等しいキー同士の相対順序は木の実装や等値を左子・右子のどちらへ入れるかなどの規約に依存し、入力順は保証されない。したがって一般には 安定ソートではない。安定性まで要るなら、比較へ到着順などの副キーを含める必要がある（これはアルゴリズムの拡張であり、「通常の」キー比較だけの性質とは別物である）。

次に掲げるデモでは、同じ値の棒が画面上で入れ替わらないよう、二分木挿入の比較を 値が異なれば値、等しければ元の位置 id の辞書式順にしている。これは 本ページの可視化のための工夫 であり、直前の段落で述べた「素のツリーソートは一般に不安定」という話を打ち消すものではない。

  1. 挿入: 入力値を順に平衡二分探索木へ挿入する（規則に従って回転や再着色などでバランスを復元する）。
  2. 取出し: 中順走査でキーを昇順に列挙し、ひとつの配列へ書き込むか、そのまま消費する。
procedure balanced_tree_sort(elements)
  T = empty balanced binary search tree
  for x in elements
    insert_balanced(T, x)
  return inorder_traversal(T)

単純な二分木ソートだけでコードは短くても入力に弱いので、実務や学習用の標準とはいえにくく、しかし二分木を使って整列させるという考え方自体はアルゴリズムの説明および他の資料構造（優先度付きキューのヒープ整列との対比など）において有用である。

クイックソートのようなインプレース志向の手法と異なり、ここでのデモでも 木の論理とは別に配列側の並びは最後まで入れ替えない と説明できないので、視覚化のために中順順序へ スワップで寄せている。実装では通常、走査結果を別バッファに書き込むだけで済ませればよい。バブルソートより改善されやすい計算量一方で、キャッシュ効率や定数係数、アロケータへの負荷などの観点では配列だけを直接いじる整列アルゴリズムに軍配が挙がることもある。