合併排序變化n + m，易混淆

Question

讓A是已按升序排序的n整數的數組。
令B爲m未整理的整數數組。
我們知道A中的一組整數與B中的一組整數不相交。描述一個算法來生成一個數組，其中所有的n + m整數已按升序排序。你的算法應該終止於O(n + m log m)時間。

我知道這應該是像合併排序，但n+m在O(n+mlogm)丟給我。任何人都可以解釋嗎？

Answer 1

我想你應該在B排列第一排序：O(mlogm)
之後，你有兩個排序數組，你需要將它們合併，這將需要：O(n+m)
現在整個過程是O(mlogm + (n+m))等於O(mlogm)。