Code golf: combining multiple sorted lists into a

Question

Implement an algorithm to merge an arbitrary number of sorted lists into one sorted list. The aim is to create the smallest working programme, in whatever language you like.

For example:

input:  ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)

input:  ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)

Note: solutions which concatenate the input lists then use a language-provided sort function are not in-keeping with the spirit of golf, and will not be accepted:

sorted(sum(lists,[])) # cheating: out of bounds!

Apart from anything else, your algorithm should be (but doesn't have to be) a lot faster!

Clearly state the language, any foibles and the character count. Only include meaningful characters in the count, but feel free to add whitespace to the code for artistic / readability purposes.

To keep things tidy, suggest improvement in comments or by editing answers where appropriate, rather than creating a new answer for each "revision".

EDIT: if I was submitting this question again, I would expand on the "no language provided sort" rule to be "don't concatenate all the lists then sort the result". Existing entries which do concatenate-then-sort are actually very interesting and compact, so I won't retro-actively introduce a rule they break, but feel free to work to the more restrictive spec in new submissions.

---

Inspired by Combining two sorted lists in Python

Answer 1

Implementation in C via Linked lists.

http://datastructuresandalgorithmsolutions.blogspot.com/2010/02/chapter-2-basic-abstract-data-types_7147.html

Answer 2

Javascript

function merge(a) {
    var r=[], p;
    while(a.length>0) {
        for (var i=0,j=0; i<a.length && p!=a[j][0]; i++)
            if (a[i][0]<a[j][0])
                j = i;

        r.push(p = a[j].shift());

        if (!a[j].length)
            a.splice(j, 1);
    }
    return r;
}

Test:

var arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]​;
alert(merge(arr));

Answer 3

Haskell: 127 characters (without indentation and newlines)

m l|all null l=[]
   |True=x:(m$a++(xs:b))
 where
   n=filter(not.null)l
   (_,min)=minimum$zip(map head n)[0..]
   (a,((x:xs):b))=splitAt min n

It basically generalizes the merging of two lists.

Answer 4

Even though it might break the rules. Here's a nice and short c++ entry:

13 Characters

l1.merge(l2); // Removes the elements from the argument list, inserts 
              // them into the target list, and orders the new, combined 
              // set of elements in ascending order or in some other 
              // specified order.

Answer 5

Haskell like (158, but more than 24 spaces could be removed.):

mm = foldl1 m where
  m [] b = b
  m a [] = a
  m (a:as) (b:bs)
   | a <= b = a : m as (b:bs)
   | true   = b : m (a:as) bs

Answer 6

Python, 181 chars

---

from heapq import *
def m(l):
 r=[]
 h=[]
 for x in l:
  if x:
   heappush(h, (x[0], x[1:]))
 while h:
  e,f=heappop(h)
  r.append(e)
  if f:
   heappush(h, (f.pop(0),f))
 return r

This runs in O(NlgM) time, where N is the total number of items and M is the number of lists.