組み合わせられた配列を並べ替える際に、並べ替えられた配列を再割り当てされた並べ替え済みの配列に追加するための最良の方法

Question

私はこの特定の問題に最適な解決策を見つけようとしています。ここで

は私がやろうとしています何の荒廃です：

• 私は2つの配列を持って、AとB
• Bは、以前A.
• 内の要素のためのスペースを作るために再割り当てされましたAは常に完全に配置された配列です。
• Bには常に少なくとも1つの要素があります。
• AとBの両方が既にソートされています。

配列をソートしたままで、AからBの要素を追加したいと思います。

例：

//Given: 
A = [1,3,5] 
B = [2,4,6, , , ] 

//Desired Result: 
B = [1,2,3,4,5,6] 

私がこれまで考えてきたこれを行うための最速の方法は次のようになります。

• N（Oを取ると、Bへのすべての要素を追加します。 ）。
• O（nlogn）のマージソートのようなものを使用して、結合された配列をソートします。

私はO（nlogn）より速くこれをやり遂げる方法があると考えています。

この場合、領域の複雑さは問題になりません。

Answer 1

マージソートのマージステップだけが必要です。マージ・ステップでは、ソートされた2つの配列を取り、それらをO（n）時間内に1つのソート済み配列に結合します。

ヘッドの代わりにAとBの末尾にマージを開始して、コピーを保存することができます。これにより、3番目の配列にマージしてからBにコピーする代わりに、Bのために割り当てたストレージでマージを実行できます。