クイックソート は、分割統治戦略に基づいた内部アルゴリズムです。この中で：

• 要素の配列は、それ以上分割できなくなるまで繰り返し複数の部分に分割されます。
• としても知られています パーティション交換ソート 。
• 要素を分割するためにキー要素 (ピボット) を使用します。
• 1 つの左側のパーティションにはピボットより小さい要素がすべて含まれ、右側の 1 つのパーティションにはキー要素よりも大きい要素がすべて含まれます。

マージソート は外部アルゴリズムであり、分割統治戦略に基づいています。この中で：

• 要素は 1 つの要素だけが残るまで何度も 2 つのサブ配列 (n/2) に分割されます。
• マージソートは、補助配列をソートするために追加のストレージを使用します。
• マージ ソートでは 3 つの配列が使用されます。そのうち 2 つは各半分の格納に使用され、3 番目の外部配列は他の 2 つをマージして最終的な並べ替えられたリストを格納するために使用され、各配列は再帰的に並べ替えられます。
• 最後に、すべてのサブ配列がマージされ、配列の要素サイズが「n」個になります。

クイックソートとマージソート

配列内の要素の分割: マージソートでは、配列は 2 つの半分 (つまり、n/2) に分割されます。一方、クイックソートの場合、配列は任意の比率に分割されます。クイック ソートでは、要素の配列を均等な部分に分割する必要はありません。最悪の場合の複雑さ: 最悪の状態では多くの比較が必要になるため、クイック ソートの最悪の場合の複雑さは O(n^2) です。一方、マージ ソートでは、最悪のケースと平均的なケースの複雑さは同じ O(n log n) になります。データセットでの使用 : マージ ソートは、サイズ (大きいか小さいか) に関係なく、あらゆるタイプのデータ セットで適切に機能します。一方、クイック ソートは大規模なデータセットではうまく機能しません。追加のストレージ スペース要件: 補助配列を格納するために追加のメモリ スペースが必要なため、マージ ソートは設定されていません。一方、クイックソートは追加のストレージを必要としないため、適切に機能します。効率 : 配列サイズやデータセットが大きい場合、マージ ソートはより効率的で、クイック ソートよりも高速に動作します。一方、配列サイズやデータセットが小さい場合は、クイック ソートの方が効率的で、マージ ソートよりも高速に動作します。ソート方法: クイックソートは、データがメインメモリ内でソートされる内部ソート方法です。一方、マージソートは、ソート対象のデータがメモリに収まらず、ソートに補助メモリが必要な外部ソート方法です。安定性 : マージ ソートは、同じ値を持つ 2 つの要素がソートされていない入力配列と同じ順序でソートされた出力に表示されるため、安定しています。一方、このシナリオではクイック ソートは不安定です。ただし、コードをいくつか変更することで安定させることができます。推奨: 配列ではクイック ソートが推奨されます。一方、リンクされたリストにはマージソートが推奨されます。参照の局所性 : クイックソートはキャッシュの局所性が優れているため、クイックソートはマージ ソートよりも高速になります (仮想メモリ環境などの多くの場合)。