Sorting sets of ordered linked lists

Question

I'm looking for an elegant, high performance solution to the following problem.

There are 256 linked lists.

• Each list contains the same types of object that among other things holds a whole number that is used to define a sort order.
• All numbers across all lists are unique
• Each individual list is sorted in ascending order by these numbers

How would you create a single ascending ordered list from all the objects from the 256 original linked lists? I'd prefer not to brute force it, and have a few other ideas, but this seems like one of those problems that there's a standard, optimal solution for.

Answer 1

You could use a priority queue that holds the “topmost” item of each of the 256 linked lists. This “topmost” item is the one that is scheduled to be inserted into the resulting list. This way, you can just take the smallest element from the priority queue, insert it into your resulting queue, and insert its next element into the priority queue:

# 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

if the individual lists are already sorted, then it's a direct application of the merge algorithm. in short: compare all the heads and pick the smallest, take it out of its list and push into your output list. repeat until all source lists are empty.

edit: Konrad's use of a priority queue (a heap) is a far more elegant and scalable solution, but maybe 256 input lists are so few that a simple compare could be faster.

Answer 3

Just merge each list with the list 128 above it. (resulting in 128 lists)
Then merge each list with the list 64 above it. (resulting in 64 lists)
Then merge each list with the list 32 above it. (resulting in 32 lists)
Then merge each list with the list 16 above it. (resulting in 16 lists)
Then merge each list with the list 8 above it. (resulting in 8 lists)
Then merge each list with the list 4 above it. (resulting in 4 lists)
Then merge each list with the list 2 above it. (resulting in 2 lists)
Then merge each list with the list 1 above it. (resulting in 1 list)
(You might use a loop for the above).

Answer 4

You don't say how long these lists are, but I assume they all fit in RAM at the same time. The first thing I would try is appending them all together, and calling my environment's builtin sort routine, and I'd see if that gave acceptable performance. It's easy to implement and wouldn't take long to test. If that didn't give acceptable performance, I'd go with the priority queue merge given by Konrad Rudolph.