StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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 <a href="http://en.wikipedia.org/wiki/Priority_queue" rel="noreferrer">priority queue</a> (eg, a <a href="http://en.wikipedia.org/wiki/Heap_(data_structure)" rel="noreferrer">heap</a>). Pseudocode:</p> <pre><code>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 </code></pre> <p>And a simple (untested!) concrete implementation in C++:</p> <pre><code>#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); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload