変更されたマージソートの実行時間とマージソートの比較

Question

ウィキペディアからhttps://en.wikipedia.org/wiki/Merge_algorithm#Application

図では、数値の中央の行を考えてみましょう（誰かがここに画像を投稿できる場合に役立ちます）。

• マージ38と27の場合、アルゴリズムの実行時間はどのようになりますか？マージ38と27をマージし、昇順にソートします。 （27、38）
• 上記の結果を43とマージし、数字を昇順でソートします。 （27、38、43）
• 上記の結果を3でマージし、昇順にソートします。 （3,27,38,43）。
• ...完全にソートされたリストがあるまで続きます。

これは非常に非効率的なソート方法です（私は直感的に言えます - 最悪の場合、追加される数値はリスト内のすべての数値と入れ替わります）私の分析を正当化する）、ソートのO（n log n）時間をマージします。

どのような考えですか？

Answer 1

説明しているアルゴリズムは、挿入ソートです。一度に1つの要素を追加することで、並べ替え順に値の増加するリストを構築しています。つまり、配列がソートされている場合は線形、平均が2次の場合はランタイムが挿入ソート - 線形と一致します。