對已排序的鏈接列表進行排序

Question

我正在尋找一個優雅的高性能解決方案來解決以下問題。

共有256個鏈接列表。

• 每個列表包含相同類型的對象，其中包含用於定義排序順序的整數。
• 所有列出所有的數字都是獨特的
• 每個單獨的列表是按升序由這些數字

你會如何創建一個升序排序從256個原來的鏈表中的所有對象列表排序？我不想強迫它，並有其他一些想法，但這似乎是存在標準的最佳解決方案的那些問題之一。

Answer 1

您可以使用優先級隊列來保存256個鏈接列表中的每個鏈接列表的「最高」項目。這個「最高」的項目是計劃插入到結果列表中的項目。通過這種方式，你可以採取從優先級隊列最小的元素，將其插入到你的結果的隊列，然後將其下一個元素到優先級隊列：

# Preprocessing: 
result = list.new() 
queue = priority_queue.new() 

foreach (list in lists): 
    queue.push(list.first()) 

# Main loop: 
while (not queue.empty()): 
    node = queue.pop() 
    result.insert(node) 
    if (node.next() != null): 
     queue.push(node.next()) 

Answer 2

如果個人名單已經排序，那麼它是一個直接應用merge algorithm。簡而言之：比較所有頭部並挑選最小的頭部，將其從列表中取出並推入輸出列表。重複，直到所有源列表都爲空。編輯：Konrad使用優先級隊列（heap）是一種更加優雅和可擴展的解決方案，但是256個輸入列表可能很少，以至於簡單的比較可能會更快。

Answer 3

只需將每個列表與它上面的列表128合併即可。 （產生128個列表）
然後將每個列表與其上面的列表64合併。 （產生64個列表）
然後將每個列表與其上面的列表32合併。 （產生32個列表）
然後將每個列表與上面的列表16合併。 （產生16個列表）
然後將每個列表與其上面的列表8合併。 （產生8個列表）
然後將每個列表與其上面的列表4合併。 （產生4個列表）
然後將每個列表與其上面的列表2合併。 （導致2個列表）
然後將每個列表與其上面的列表1合併。 （導致1個列表）
（您可以使用上面的循環）。

Answer 4

你不會說這些列表有多長，但我認爲它們都可以同時裝入RAM中。我會嘗試的第一件事就是將它們全部附加在一起，然後調用我的環境的內置排序例程，然後我會看看它是否能夠提供可接受的性能。這很容易實現，不需要很長時間來測試。如果這沒有給出可接受的表現，我會選擇康拉德魯道夫給出的優先隊列合併。