Cache-oblivious distribution sort とは

キャッシュを知らない分布のソートは、比較ベースのソートアルゴリズムです。クイックソートに似ていますが、ソートする要素の数が大きすぎて操作が行われるキャッシュに収まらない設定のために設計された、キャッシュを知らないアルゴリズムです。外部メモリモデルでは、サイズが Z {\displaystyle Z} のキャッシュと長さ L {\displaystyle L} のキャッシュラインを持つマシン上の一種の N {\displaystyle N} アイテムを実行するために必要なメモリ転送の数は、高キャッシュの仮定の下で O ( N L log Z N ) {\displaystyle O({\frac {N}{L}}\log _{Z}N)} それ Z = Ω ( L 2 ) {\displaystyle Z=\Omega (L^{2})} 。この数のメモリ転送は、比較ソートに漸近的に最適であることが示されています。この分布ソートは Θ ( N log N ) {\displaystyle \Theta (N\log N)} の漸近的に最適な実行時の複雑さも達成する。