Arrays#sort

JavaにはArrays#sortというメソッドがあって配列をソートすることができる．ソートする対象がプリミティブ型だとquick sortで実装され，オブジェクトだとmerge sortで実装している．オブジェクトのソートはstableであるという仕様のためだと思われる．

さらに，どちらの場合も配列のサイズが小さい場合はinsertion sortで実装されている．merge sortもquick sortも分割して再帰的に実行されるため，分割された配列の要素数が小さくなった時点で，insertion sortに切り替わっている．insertion sortはO(n^2)なんだけどもシンプルな実装なので短い配列の場合はそっちの方が効率がいいということだろう．

その他いくつか面白いなと思った点．

quick sortのpivot

配列を2等分(サイズが大きい場合は8等分)して，配列の両端と分割点の値の中央値をpivotにしている．こうするとpivotよりも大きいものと小さいものを偏りなく分割できそう．

浮動小数点数の扱い

javaの浮動小数点数では-0.0と0.0が等しく，NaNは比較可能でない．そのため，-0.0を0.0にして，NaNを配列の最後に置いてNaNを除いた状態でソートした後に，-0.0があった数だけ0.0を-0.0に戻す．というわけで以下のような並び順になる

	double[] doubles = new double[]{Double.NaN, 3.14, -42, 0.0, -0.0};
	Arrays.sort(doubles);
	System.out.println(Arrays.toString(doubles)); // [-42.0, -0.0, 0.0, 3.14, NaN]