Project Name: ソート（クイックソート・マージソートの改良アルゴリズムの提案）

松原正和(matsubara masakazu)

■概要

　クイックソート・マージソートの改良アルゴリズムを提案してみます。

mmSort

Quicksortの比較回数削減を狙ったアルゴリズム。
Median of 5 Quicksort をベースとしている。
不安定ソート

mmsSort

Dual-pivot stable Quicksortとでもいうべきアルゴリズム。
Merge Sort のように作業領域を用いる。
3 way patition Quicksort アルゴリズムも併用する。
安定ソート

MatMmsSort

MatSortとmmsSort を組み合わせたアルゴリズム
作業領域の使用量は対象配列の1/10程度（任意に指定可能）
速度的にはmmsSortにやや劣る。
安定ソート

mmsSort (Half memory)

mmsSort をメモリ使用量を半分に削減したアルゴリズム。
MergeSortを併用する。
安定ソート

Many Pivot Sort

Quicksortのピボット値選択方法改善アルゴリズム（mmSortに少し劣ることが多い）
事前に多くのピボット値候補を決めておく。精度の高い（中央値に近い）
ピボット値を得ることができる。
不安定ソート

MasSort

3-Way Merge Sortアルゴリズムの一種
ヒープツリーやトーナメントツリーを使わず、サブツリーの先頭値の値で
サブツリーをソートし、１つの整数型変数のみでその状態を管理する。
4-Way 版もある。(Javaによる実装ではやや遅い) 安定ソート

MatSort

作業領域のメモリ使用料量削減を狙ったMerge Sortの改善アルゴリズム
MasSort等、他のMerge Sort系アルゴリズムを内部的に併用する。
作業領域サイズを配列サイズの1/10程度に圧縮しても数％程度の性能低下
で済む。むしろ高速になるケースもある。
安定ソート

■詳細

詳細は以下より参照のこと

sort

■このコンテンツの扱いについて（著作権・ライセンス・アルゴリズムの利用について）

　このコンテンツの目的は著作物の配布ではなく、アルゴリズムの提案です。ここで提案 するアルゴリズム自体は特許や著作権に左右されず改変も含めて自由に再実装（他の言語 への移植を含む）をしていただいて構いません。またJavaによる実装が提供されますが、 この実装(著作物)はMITライセンスに基づき商用を含め自由にご利用いただけます。