合併排序列表

Question

我有四個排序列表，我想合併成一個排序列表。
什麼是最有效的方法呢？如果實施可以並行進行，那麼這是一個優點。

Answer 1

這是merge sort的合併部分。

只需將每個列表頭部的四個元素中的最小值轉儲到輸出列表中。重複，直到所有列表都爲空。假設min4是固定成本，那麼這只是O（N）。

如果您有更多信息（如列表的範圍），您可能可以稍微改進一些，但我不認爲這會影響漸近複雜性。