図書館ソート
ここで binarysearch(A, k) は配列 A の最初の k 個の要素に二分探索を適用する。ただし隙間は無視する。挿入は要素が詰まったところより隙間を優先する。
しかしながら O(n) の挿入ソートとは異なり、高確率でクイックソートと同じクラスの O(n log n) で実行できることが示されている。この改良のために使われた仕組みはスキップリストのものとほぼ同様である。論文では、完全な実装も、挿入や調整(rebalance)のような重要な部分の正確なアルゴリズムも示されていない。図書館ソートが他のソートアルゴリズムと比べて現実的にどの程度有効であるかを議論するには、さらなる情報が必要となる。
基本的な挿入ソートと比べて、図書館ソートの欠点は隙間のための空間を要することである。スペースの量や配置は実装による。論文において、必要な配列の長さは (1 + ε)n だとされているが、ε の選び方は何も推奨されていない。
挿入ソートの弱点の一つに、メモリへの書き込みが高コストである時に、多くの回数の swap 操作が負荷になりうるというものがある。図書館ソートは要素の移動が少なくなるように改良されているので、挿入段階が多少改善される可能性があるが、調整の段階で追加のコストを要する。加えて、ランダムなデータセットからの挿入操作がキャッシュから外れたメモリにアクセスする可能性があり、特に大きなデータセットについて、参照の局所性がマージソートに劣る。