[解決済み] Java の Arrays.sort メソッドは、なぜ型によって2つの異なるソートアルゴリズムを使用するのですか？

疑問点

Java 6の Arrays.sort メソッドでは、プリミティブの配列にはクイックソートを、オブジェクトの配列にはマージソートを使用します。私は、ほとんどの場合、Quicksort は merge sort よりも高速で、メモリコストも少ないと考えています。私の実験もそれを裏付けています。しかし、どちらのアルゴリズムも O(n log(n)) です。では、なぜ異なる型に対して異なるアルゴリズムが使用されるのでしょうか？

どのように解決するのか？

最も可能性の高い理由: クイックソートが 安定していない すなわち、等しいエントリはソートの間にそれらの相対的な位置を変更することができます。とりわけ、これはすでにソートされた配列をソートする場合、それが変更されないかもしれないことを意味します。

プリミティブ型は同一性を持たないので（同じ値を持つ2つのintを区別する方法がない）、これはそれらのために重要ではありません。しかし、参照型については、いくつかのアプリケーションで問題を引き起こす可能性があります。したがって、安定したマージソートがそれらに使用されます。

原始的な型に対して (保証された n*log(n)) 安定したマージソートを使用しない理由は、配列のクローンを作成する必要があるからかもしれません。参照型では、参照されるオブジェクトは通常、参照の配列よりもはるかに多くのメモリを消費するため、これは一般的には問題ではありません。しかし、プリミティブ型では、配列のクローンを作成すると、メモリ使用量が2倍になります。