メモリ転送回数の増加を抑えつつ、ワークメモリを併用することで高速な安定ソートを実装してみました。いくつかの高速化のアイディアを導入することで乱数データなどで一般的なクイックソート実装(3つのメディアン・5つのメディアン)に対してやや速い程度のパフォーマンスとなりました。ちなみにワークメモリは作業配列と同サイズが必要になります。定格運転で独自のベンチマークテストに基いた結果。異なるテストでは異なる結果になる可能性もあります。ソースコードおよびベンチマーク結果の生データアルゴリズム解説1.ソート対象から適当に8(要素数が小さい場合は5個)取り出してソートし、3番目と6番目(または2番目と4番目)をピボット値として採用します。2.ソート対象を先頭から走査し、次のように振り分けます。ピボット1以下の値(value≦pivot1)はソート対象の先頭から詰めていきます。ピボット2以上の値(pivot2≦value)は作業領域の後ろから前方向に詰めていきます。ピボット1より大きく、ピボット2より小さい値(pivot1<value<pivot2)は作業領域の前方から後ろ方向に詰めていきます。3.作業領域の「pivot1<value<pivot2」と「pivot2≦value」をソート対象の「value≦pivot1」の後ろに追加します。(「pivot2≦value」は順序を反転してコピーします)4.「pivot2≦value」・「pivot1<value<pivot2」・「value≦pivot1」をそれぞれ再起でソートします。アルゴリズムに切り替えます。乱数/ユニーク乱数/前半ソート済み・後半ランダム/昇順ソート済み/降順ソート済み/全て同値で計測を行いました。乱数/ユニーク乱数でクイックソートをやや上回る結果を得ました。10,000,000件の乱数データで以下のような結果となりました。1.084倍)※ベンチマークの信頼性については、後述します。昇順ソート済み/降順ソート済みはあまり良くない結果となりました。一般的なクイックソートでは、昇順ソート済みは全くメモリ転送が発生しません。降順ソート済みも初回のパーティション操作のみメモリ転送が発生し、この時点で(ほぼ)ソート済みとなるため、ほとんどメモリ転送が発生せず、乱数データよりかなり高速化します。mmsSortでは、通常時と同じようにメモリ転送が発生してしまうため乱数データと同程度の計算量となり、良くない結果になってしまったようです。ちなみに、前半ソート済み・後半ランダム/昇順ソート済み/降順ソート済みはマージソート系のアルゴリズムがとても高速に動作します。比較回数に関しては、mmsSortは一般的なクイックソート系アルゴリズムと同じくらいかやや少ないくらいとなりました。比較回数は、一般的にクイックソート系のアルゴリズムよりマージソート系のアルゴリズムのほうが概ね少なくなっています。このことは、メモリ転送が高速で、あまりこれがネックにならない場合や比較関数が重い処理の場合などで、マージソートのほうがクイックソートより速くなる可能性があることを示します。(比較のキーが文字列でありかつロケールを考慮しなければいけなかったり、ハッシュオブジェクトからの値の取り出しなど、比較関数が重くなるケースは多いかもしれません)ベンチマークでは以下のアルゴリズムの比較を行っています。3)のベンチマーク結果に対しT検定を行ってみました。となり有意な結果を得ました。ついても共に十分に大きな値を得ることができました。(p<0.05)効果量d=3.927094512最後に今回作成したアルゴリズム、mmsSortはクイックソートとマージソートの中間程度のパフォーマンスを想定して設計しましたが、実装を様々に最適化することでクイックソートをやや上回る結果を得ることができました。比較回数はマージソート系に劣るし、昇順ソート済み・降順ソート済みデータに対しては他のアルゴリズムのほうが良好な結果となりました。(mmsSortが遅くなったのではなく、他のアルゴリズムが速くなったため)。5)を上回ることができ、一定の成果を得ることができたと思います。Mk-2というフリーのSQL開発環境&ER図ツール作ってます。upLoginユーザーは見つかりませんでした。