最好的方法添加排序陣列到重新分配的排序陣列，同時排序組合陣列

Question

我想弄清楚這個特定問題的最佳解決方案。

這裏是什麼，我試圖做的破敗：

• 我有兩個數組，A和B.
• B在先前重新分配，以騰出空間爲元素A.
• A總是一個完全填充的數組。
• B總是有至少一個元素。
• A和B都已排序。

我想添加到B的元素，同時保持數組排序。

例：

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

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

，我認爲到目前爲止，這樣做的最快方法是：

• 添加所有A與B的元素，將採取爲O（n ）。
• 對合並數組進行排序，使用類似O（nlogn）的合併排序。

我想弄清楚有一種方法做得比O（nlogn）快。

空間複雜度在這種情況下不是問題。

Answer 1

您只需要mergesort的合併步驟。合併步驟需要兩個已排序的數組，並將它們組合爲O（n）時間的一個已排序數組。

通過在A和B的尾部而不是頭部開始合併，可以節省一些時間複製。這可以讓你在你爲B分配的存儲空間中執行合併，而不需要合併到第三個數組中，然後將其複製回B.