1

2 つのソートされたリストがあり、それらを 1 つのソートされたリストに結合しようとしているマージソートの最後から 1 つのステップでは、ロジックはどのようになりますか?

これが私の素朴な考えです: リスト #1 の各要素を取り、それをリスト #2 の各要素と比較し、リスト #2 での位置を見つけます。基本的には挿入ソートに似ています。

しかし、明らかに、これは O(n^2) の複雑さを与えるため、これがどのように起こるかではありません。ただし、マージソートは O(nlogn) です。では、最終段階はどのように行われるのでしょうか。

4

2 に答える 2

1

マージソートを使用しています。マージソートには個別のソートアルゴリズムはありません。それはソートアルゴリズムです。

したがって、元のリストは既にソートされているため、最小の要素が常に先頭にあります。A と B を比較します。2 つのうち小さい方を取り、それを結果リストの最後に追加します。両方のソース リストが空になるまで繰り返します。

于 2013-08-23T14:39:39.790 に答える