なるのを防ぐことができます。基準値(ピボット)を単純に「配列の中央」にするのではなく、「配列の先頭」・「配列の中央」・「配列の最後尾」の3つの中の中央値を取るようにするとピボットが偏るのを防ぐことができます。下のように書くことができます。安定性・内部ソートかどうかクイックソートは、非常な高速でソートである一方、同じ値の順序関係が崩れてしまうデメリット(安定ソートではない)があります。クイックソートは外部メモリ(作業用配列)を使わずにソートできるため、内部ソートです。マージソートのしくみマージソートでは、まず下のようにデータを半分ずつに分割していきます。つぎに、分割した各データを少しずつ整列(マージ)していきます。上の2つの過程でソートを行うのがマージソートです。分割部分は配列の中央よりも左側にあるデータ(左半分)と配列の中央よりも右側にあるデータ(右半分)の2つにわけて再帰的に分割していきます。マージソートは、全体の配列を小さく分けてから徐々にソートしていくため、クイックソートと同じく分割統治法を用いたソートといえます。マージ部分マージ部分は、作業用配列をうまく使うことで表現ができます。左半分のデータをそのまま作業用配列にコピーします。つぎに右半分のデータはもとの配列の逆順にコピーします。すると、作業用配列の両端が小さい値に、真ん中が大きい値となりますね。あとは、両端の「先頭」と「最後尾」のどちらか小さい値の方を元のデータ配列に値を入れていく操作を作業用配列のすべてのデータがコピーされるまで続ければマージ完了です。マージソートを行うプログラムは下のように書くことができます。