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

C#

static void f(params int[][] b)
{
    var l = new List<int>();
    foreach(var a in b)l.AddRange(a);
    l.OrderBy(i=>i).ToList().ForEach(Console.WriteLine);
}
static void Main()
{
    f(new int[] { 1, 4, 7 },
      new int[] { 2, 5, 8 },
      new int[] { 3, 6, 9 });
}

Answer 2

I don't think you can get much better than @Sykora's response, here, for Python.

Changed to handle your inputs:

import heapq
def m(i): 
    return list(heapq.merge(*i))

print m(((1, 4, 7), (2, 5, 8), (3, 6, 9)))

For the actual function, 59 characters, or the 52 in reduced version:

import heapq
def m(i): return list(heapq.merge(*i))

This also has the benefit of using a tested and true implementation built into Python

Edit: Removed the semi-colons (thanks @Douglas).

Answer 3

Common Lisp already has a merge function for general sequences in the language standard, but it only works on two sequences. For multiple lists of numbers sorted ascendingly, it can be used in the following function (97 essential characters).

(defun m (&rest s)
  (if (not (cdr s))
      (car s)
      (apply #'m
             (cons (merge 'list (car s) (cadr s) #'<)
                   (cddr s))))) 

edit: Revisiting after some time: this can be done in one line:

(defun multi-merge (&rest lists)
  (reduce (lambda (a b) (merge 'list a b #'<)) lists))

This has 79 essential characters with meaningful names, reducing those to a single letter, it comes out at 61:

(defun m(&rest l)(reduce(lambda(a b)(merge 'list a b #'<))l))

Answer 4

OCaml in 42 characters:

let f=List.fold_left(List.merge compare)[]

I think I should get extra credit for 42 exactly?

Answer 5

Python: 113 characters

def m(c,l):
    try:
        c += [l[min((m[0], i) for i,m in enumerate(l) if m)[1]].pop(0)]
        return m(c,l)
    except:
        return c

# called as:
>>> m([], [[1,4], [2,6], [3,5]])
[1, 2, 3, 4, 5, 6]

EDIT: seeing as talk of performance has come up in a few places, I'll mention that I think this is pretty efficient implementation, especially as the lists grow. I ran three algorithms on 10 lists of sorted random numbers:

• my solution (Merge)
• sorted(sum(lists, [])) (Built-in)
• Deestan's solution which sorted in a different way (Re-implement)

EDIT2: (JFS)

The figure's labels:

• merge_26 -- heapq.merge() from Python 2.6 stdlib
• merge_alabaster -- the above code (labeled Merge on the above figure)
• sort_builtin -- L = sum(lists,[]); L.sort()
• Deestan's solution is O(N**2) so it is excluded from the comparison (all other solutions are O(N) (for the input provided))

Input data are [f(N) for _ in range(10)], where f() is:

max_ = 2**31-1
def f(N):
    L = random.sample(xrange(max_), n)
    L.sort()
    return L
f.__name__ = "sorted_random_%d" % max_

NOTE: merge_alabaster() doesn't work for N > 100 due to RuntimeError: "maximum recursion depth exceeded".

To get Python scripts that generated this figure, type:

$ git clone git://gist.github.com/51074.git

Conclusion: For reasonably large lists the built-in sort shows near linear behaviour and it is the fastest.

Answer 6

resubmitted

Python - 74 chars (counting whitespace and newlines)

def m(i):
 y=[];x=sum(i,[])
 while x:n=min(x);y+=[n];x.remove(n)
 return y

i is input as list of lists

Usage:

>>> m([[1,5],[6,3]])
[1, 3, 5, 6]