MergeSort実装の安定性

Question

mergesortの実装は安定性に影響しますか？

たとえば、配列を使用してマージソートを実装すると、マージソートのリンクリスト実装よりも安定性が低くなりますか？

Answer 1

配列またはリンクされたリストのマージソートのトップダウン（再帰的）実装とボトムアップ（反復）実装のほとんどの実装は安定しています。重要な要素はマージ関数です。マージ関数が "右"要素の前に等しい "左"要素を移動する限り、安定します。比較は "left"要素< = "right"要素か、または比較のために使用されるよりも少ない、C++標準ライブラリの場合は、その比較が "right"要素< "left"要素であるため、 "left"要素< = "right"要素の場合は移動します。

もう1つの可能性のある問題は、小さなグループの要素に対して非安定ソート方法を使用したハイブリッドマージソートにあります。

通常、隣接する要素を交換するソート（バブルソートなど）は通常安定していますが、非隣接要素をスワップするソート（通常はクイックソートなど）は通常安定しません。

Answer 2

マージソートは、両方で安定している必要があります。あなたがリストや配列を使うのは、それを何を使っているかによります。

Answer 3

並べ替え方法は、配列内の等しいキーを持つ要素の相対的な順序を保持すると安定します。

トップダウンとボトムアップの両方の実装は安定したアプローチです。その配列やリンクされたリストから独立しています。