図書館ソート
要素数 n の配列が与えられたとする。これに隙間を入れて、要素数 (1 + ε)n にする。以下、挿入と調整の操作を繰り返す (log n 回)。挿入段階では、挿入済みの要素と同じ数の要素を挿入する。挿入済みの部分に二分探索を適用することで挿入位置を見つけ、そしてスペースが見つかるまで要素を swap していく。調整段階では、配列の各要素の間に隙間を挿入する。
このアルゴリズムの重要な手順は次の3つである:
1. 二分探索: 挿入済みの要素からなる部分に二分探索を適用することで、次の要素の挿入位置を見つける。区間の中央がスペースだった時は、単に左か右の方へ移動すればよい。
2. 挿入: 見つかった位置に要素を挿入し、次のスペースまで後ろの各要素を1つずつずらしていく。
3. 調整: 配列の各要素の間にスペースを挿入する。これには線形時間がかかる。このアルゴリズムは log n 回の繰り返しからなるので、調整にかかる時間は全体で O(n log n) 時間だけである。