Sort sets of ordered linked lists

Question

I am looking for an elegant and high-performance solution to the following problem.

There are 256 linked lists.

• Each list contains the same types of objects that by the way contains an integer that is used to determine the sort order.
• All numbers in all lists are unique.
• Each individual list is sorted in ascending order by these numbers.

How would you create one ascending ordered list from all objects from 256 source linked lists? I would prefer not to use this command and offer some other ideas, but this seems like one of those problems in which there is a standard, optimal solution for.

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

, . : , . , .

edit: Konrad (a heap) - , , , 256 , .

Answer 3

128 . ( 128 )
64 . ( 64 )
32 . ( 32 )
16 . ( 16 )
8 . ( 8 )
4 . ( 4 )
2 . ( 2 )
1 . ( 1 )
(You can use a loop for above).

Answer 4

You do not say how long these lists are, but I assume that they all fit into RAM at the same time. The first thing I would like to try is to add them all together and call my environment built into the sorting procedure, and I will see if this provides acceptable performance. It is easy to implement and does not take much time to check. If this did not give acceptable performance, I would go with the merger of the queue of priorities given by Conrad Rudolph.