Merging 8 sorted lists in c++, which algorithm should I use

Question

I have 8 sorted lists that I need to merge into 1 sorted list. I don't know the best way to do this. I was thinking of the following:

void merge_lists_inplace(list<int>& l1, const list<int>& l2)
{
    list<int>::iterator end_it = l1.end();
    --end_it;
    copy(l2.begin(), l2.end(), back_inserter(l1));
    ++end_it;
    inplace_merge(l1.begin(), end_it, l1.end());
}

list<int> merge_8_lists(list<int>[8] lists)
{
    merge_lists_inplace(lists[0], lists[1]);
    merge_lists_inplace(lists[2], lists[3]);
    merge_lists_inplace(lists[4], lists[5]);
    merge_lists_inplace(lists[6], lists[7]);

    merge_lists_inplace(lists[0], lists[2]);
    merge_lists_inplace(lists[4], lists[6]);

    merge_lists_inplace(lists[0], lists[4]);

    return lists[0];
}

But would it be better to just worry about the sorting last?

list<int> merge_8_lists(list<int>[8] lists)
{
    for (int i = 1; i < 8; ++i)
        copy(lists[i].begin(), lists[i].end(), back_inserter(lists[0]));        
    lists[0].sort();
    return lists[0];
}

Side note: I don't care that the lists are modified.

Answer 1

You could try applying the merge sort one at a time to each of the lists:

http://en.wikipedia.org/wiki/Merge_sort

This has the algorithm for the merge sort. Essentially you'd go with list 1 and 2 and merge sort those. Then you'd take that new combined list and sort with list 3, and this continues until you have one fully sorted list.

EDIT:

Actually, because your lists are already sorted, only the last part of the merge sort would be needed. I would iteratively combine the lists into bigger and bigger parts all the while sorting each of those bigger lists until you have your full list, which is essentially what the merge sort does after it's done with its divide and conquer approach.

Answer 2

A simple extension of merge sort's merge phase can do this in O(n lg m) time (where n = total number of items and m = number of lists), using a priority queue (eg, a heap). Pseudocode:

Let P = a priority queue of the sorted lists, sorted by the smallest element in each list
Let O = an empty output list
While P is not empty:
  Let L = remove the minimum element from P
  Remove the first element from L and add it to O
  If L is not empty, add L to P

And a simple (untested!) concrete implementation in C++:

#include <list>
#include <set>

template<typename T>
struct cmp_list {
    bool operator()(const std::list<T> *a, const std::list<T> *b) const {
        return a->front() < b->front();
    }
};

template<typename T>
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input)
{
    // Use a std::set as our priority queue. This has the same complexity analysis as
    // a heap, but has a higher constant factor.
    // Implementing a min-heap is left as an exercise for the reader,
    // as is a non-mutating version
    std::set<std::list<T> *, cmp_list<T> > pq;

    for ( typename std::list<std::list<T> >::iterator it = input.begin();
            it != input.end(); it++)
    {
        if (it->empty())
            continue;
        pq.insert(&*it);
    }

    while (!pq.empty()) {
        std::list<T> *p = *pq.begin();
        pq.erase(pq.begin());

        output.push_back(p->front());
        p->pop_front();

        if (!p->empty())
            pq.insert(p);
    }
}

Answer 3

If performance is not a concern, I would sort the lists last. The code is more readable, shorter, and less likely to get screwed up by someone revisiting the code in the future.

Answer 4

This is a standard (although 8-way) merge sort.

Basically you "open" the eight sorted lists then begin processing them, extracting the lowest value each time, something like:

# Open all lists.

open newlist for write
for i = 1 to 8:
    open list(i) for read
end for

 

# Process forever (break inside loop).

while true:
    # Indicate that there's no lowest value.

    smallidx = -1

    # Find lowest value input list.

    for i = 1 to 8:
        # Ignore lists that are empty.

        if not list(i).empty:
            # Choose this input list if it's the first or smaller
            #  than the current smallest.

            if smallidx = 1:
                smallidx = i
                smallval = list(i).peek()
            else:
                if list(i).peek() < smallval:
                    smallidx = i
                    smallval = list(i).peek()
                end if
            end if
        end if
    end for

 

    # No values left means stop processing.

    if smallidx = -1:
        exit while
    end if

    # Transfer smallest value then continue.

    smallval = list(smallidx).get()
    newlist.put(smallval)
end while

Answer 5

Basically you are doing part of multiway mergesort, except your stuff is already sorted...

http://lcm.csa.iisc.ernet.in/dsa/node211.html

Just find the lowest in each array (almost use as stacks) and put that in your output till all stacks are empty...

Answer 6

You want a merge sort. Your lists are already split but not all the way to the smallest level. You may want to do this:

unsorted_list = concatenate(list[0], list[1], list[2], ... , list[7]);
sorted_list = merge_sort(unsorted_list);

That shouldn't be a time/memory consuming operation because the concatenation should add a link from the last node in in a list to the first element of the next list.