合併排序後的數組，什麼是最佳時間複雜度？

Question

我有m個數組，每個數組的長度爲n。每個數組都進行排序。我想創建一個長度爲m * n的單個數組，包含前面數組的所有值（包括重複值），並進行排序。我必須合併這些陣列..

我認爲最佳的時間複雜度M * N *日誌（M）

這裏的算法的草圖..

我創建支持數組h的長度爲m，包含每個數組的第一個元素的所有值。

然後我排序這個數組（m log m），並將最小值移到輸出數組。

然後，我將它移動的值替換爲下一個移動的值。其實我沒有取代它，但我把它插入右邊（排序）的位置。我認爲這需要記錄。

我再重複這個對所有m * n個值...因此M * N * log M的

我的問題..你能想到一個更有效的算法嗎？如果mnlogm實際上是最優的，你至少能想到一個更簡單，更優雅的算法嗎？

Answer 1

複雜性是正確的！但是，算法思路中存在一個小缺陷：您無法在log m中的排序數組中插入項目。你可以在二進制搜索中找到它的位置，但你可能需要移動元素才能將它放置在那裏。要解決這個問題，你可以使用堆數據結構來代替！

多路合併（這是您算法的通用名稱）通常通過另一個'合併'數據結構來實現：比賽樹。你可以在Knuth的「計算機程序設計藝術」（排序章節，iirc）中找到描述。在這個具體情況下，與堆相比，它在理論上和實踐中具有較低的常數因子。

如果你想看實現，我敢肯定GNU C++標準庫並行擴展中的並行多路合併是以這種方式實現的。

編輯：我引用了錯誤的書，現在已經修復了。

Answer 2

你可以做的最好的是O（m * n + d）。類似於計數排序：http://en.wikipedia.org/wiki/Counting_sort如果您知道可能的值範圍（d，比如說），則可以初始化一個長度爲d的數組，然後掃描每個m數組，每個數組中添加1到每個「bin」到那個垃圾箱。然後，在d中爲每個值添加長度爲m * n的新數組，然後添加bin的許多計數。