図書館ソートを使用する

図書館ソート (library sort、空隙付き挿入ソートとも呼ばれる) は、整列済みデータを 隙間（空きスロット）を挟みながら 棚に並べるイメージのソートである。新しい本（要素）を挿入するとき、適切な隙間に直接置ければ周りを大きく動かさずに済む。隙間が足りなければ、近くの空きへ本をずらしてから挿入する。

挿入位置の探索に二分探索を使えるため、ランダムな入力に対しては 比較回数が O(n log n) になりやすい（詳細は隙間の取り方や再配置の戦略に依存する）。古典的な 挿入ソート と同じく 安定ソート にできる。

  1. 棚（作業配列）: 要素数より長いバッファを用意し、値が入っていないマスを 空き とみなす。
  2. まだ挿していない値 を1つずつ取り出す（入力順はデモではシャッフル後の並び）。
  3. 探索: 棚上の値だけを対象に、挿入すべき 順序上の位置 を二分探索で求める。
  4. 挿入: その区間に空きがあればそこへ値を書き込む。なければ 近い空きまで値を隣接交換でずらし、空いたマスへ書き込む。
  5. 終了: すべての値を置き終えたとき、左から右へ読めば昇順になっている（値同士の間に空きが残ってもよい）。

以下は手順を抽象的に示した疑似コードである。

procedure library_sort_insert(keys, capacity)
  buf[0 .. capacity-1] = empty
  for each key in keys
    find sorted rank r of key among filled cells of buf
    choose a free cell at or near rank r (open with shifts if needed)
    buf[chosen] = key

デモでは 30マスの棚 に 15個の値 を順に挿入する。空きマスは灰色の短いバーで示す。実装の論文レベルの工夫（一定割合の隙間の維持や全体の再配置など）は省略し、二分探索で順序位置を決め、必要なら右または左の空きへ向かって隣接スワップでずらす ところまでを追えるようにしている。

概念的には「棚に空きを残しておく」ことで 挿入ソート で毎回長いシフトが続く状況を緩和しようとする発想である。実装や定数の取り方次第では再配置のコストが支配的になる場合もあるため、用途に合わせてマージソートやヒープソートなどとも比較したい。