ソート手法にはいろいろなアルゴリズムがあります。2019年5月、ソートアルゴリズム別の処理時間を比較しました。それぞれのソート手法には、基本型と改良型があります。クイックソート表に示したソートアルゴリズムの詳細は、拙著の「超最速ソートアルゴリズム解説」を参照してください。ソートの計算量ソート手法は、アルゴリズムのデータ比較回数により「どのくらい計算に時間がかかるか」という計算量O(オーダー)で実行効率を比較することができます。基本型のソート手法の計算量は、O(N×N)でデータ数Nの二乗に比例します。改良型のソート手法の計算量は、O(N×logN)でデータ数NとNの対数の積に比例します。O(N×N)、O(N×logN)、O(N)のグラフを下記に示します。ソートの計算量データ件数が増えるごとに、それぞれの計算量の格差は開いていきます。究極のソートアルゴリズムデータの大小比較によるソートでは、計算量O(N×logN)が限界だと考えられています。この限界を超える手法はないのでしょうか?「超最速ソートアルゴリズム解説」で紹介したダイレクトマップソートは、計算量O(N)のソートです。15000件規模のデータで、速さで定評のあるクイックソートよりも10倍も速く動作するので驚きです。ダイレクトマップソートは、究極を超えたソートアルゴリズムです。本を執筆したときは、15000規模のデータで計測しました。データ量が増加した場合はどうなのだろうと今回計測しました。16bitソートキーで、データ量を5000件~55000件まで5000件刻みでソート処理時間を計測しました。シェルソート、ヒープソート、クイックソート、ダイレクトマップソートについて比較しました。計測に使用したPC情報を次に示します。最適化/O2)計測時間の絶対値は、PCのスペックにより変化しますので、データ量増加による処理時間の増加に注目してください。16,834msソートの計測結果グラフの縦軸は計測時間で単位は[ms]で、横軸はデータ件数です。シェルソート、ヒープソート、クイックソートは、データ量の増加に伴い計算量も徐々に増加していきます。それに対して、ダイレクトマップソートはデータ数Nに比例して計算量は増えますが、その増加はわずかです。データ量55000件規模で、ダイレクトマップソートは712msです。クイックソートは7,477ms、ヒープソートは10,288ms、シェルソートは16,834msです。ダイレクトマップソートダイレクトマップソートは、クイックソートに比べて10倍速く動作しました。まとめシェルソート、ヒープソート、クイックソート、ダイレクトマップソートについて処理時間を計測して比較しました。ダイレクトマップソートは、速さで定評のあるクイックソートよりも10倍も速く動作することがわかりました。