Sortowanie zestawów uporządkowanych list połączonych

Możesz użyć kolejki priorytetowej, która przechowuje „najwyższy” element każdej z 256 połączonych list. Ten „najwyższy” element to ten, który ma zostać wstawiony do listy wynikowej. W ten sposób możesz po prostu wziąć najmniejszy element z kolejki priorytetowej, wstawić go do kolejki wynikowej i wstawić następny element do kolejki priorytetowej:

# 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())

jeśli poszczególne listy są już posortowane, jest to bezpośrednie zastosowanie algorytmu scalania. w skrócie: porównaj wszystkie głowice i wybierz najmniejszą, usuń ją z listy i wepchnij do listy wyników. powtarzaj, aż wszystkie listy źródeł będą puste.

edytuj: użycie przez Konrada kolejki priorytetowej (sterty) jest znacznie bardziej eleganckim i skalowalne rozwiązanie, ale może 256 list wejściowych jest tak mało, że proste porównanie może być szybsze.

Po prostu połącz każdą listę z listą 128 nad nią. (co daje 128 list)
Następnie połącz każdą listę z listą 64 nad nią. (co daje w wyniku 64 listy)
Następnie połącz każdą listę z listą 32 powyżej. (co daje w wyniku 32 listy)
Następnie połącz każdą listę z listą 16 znajdującą się powyżej. (w wyniku jest 16 list)
Następnie połącz każdą listę z listą 8 nad nią. (w wyniku powstaje 8 list)
Następnie połącz każdą listę z listą 4 nad nią. (co daje 4 listy)
Następnie połącz każdą listę z listą 2 nad nią. (w wyniku są 2 listy)
Następnie połącz każdą listę z listą 1 powyżej. (co daje 1 listę)
(Możesz użyć pętli do powyższego).

Nie mówisz, jak długie są te listy, ale zakładam, że wszystkie mieszczą się w pamięci RAM w tym samym czasie. Pierwszą rzeczą, którą bym spróbował, jest dodanie ich wszystkich razem i wywołanie wbudowanej procedury sortowania mojego środowiska, i zobaczę, czy daje to akceptowalną wydajność. Jest łatwy do wdrożenia i nie zajmie dużo czasu na przetestowanie. Gdyby to nie dawało akceptowalnej wydajności, wybrałbym połączenie kolejki priorytetowej podane przez Konrada Rudolpha.