views:

2243

answers:

25

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 http://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python

+6  A: 
Alabaster Codify
Test you function for `[[1]*10 for _ in range(100)]` input (expected output `[1]*1000`). I've tested `L = sum(lists, []); L.sort()`; it is faster than version based on `heapq.merge()` (Python 2.6) for the inputs I've tried`
J.F. Sebastian
`len(m([], [[1]*10 for _ in range(100)]))` must be `1000`, but it returns `994`.
J.F. Sebastian
Oh cool, that's an interesting bug! In golfifying my solution, I used the `except:` which masks the "RuntimeError: maximum recursion depth exceeded in cmp" you get when l is very long. The "never use a bare except" rule wins again.
Alabaster Codify
I've added updated performance graph. And a link to source code if someone'd like to reproduce it.
J.F. Sebastian
+6  A: 

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]
Deestan
That's pretty much doing the combine and sort - you've just implemented the sort yourself.
Douglas Leeder
...and inefficiently as well ;)
Christoph
@Christoph: Yeah; spirit of Code Golf. :)
Deestan
@Douglas: Yeah, I know. My original submission is the one now given as "cheating!" in the question.
Deestan
Not only are you sorting, you're using selection sort, which has _best-case_ O(N^2) behavior.
Adam Rosenfield
Indeed. It is O(N**2) http://i403.photobucket.com/albums/pp111/uber_ulrich/_103sorted_random_2147483647.png
J.F. Sebastian
A: 

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).

Lasse V. Karlsen
And you don't need the semi-colons...
Douglas Leeder
Heh, of course, I'm just in the habit of adding them. Good catch.
Lasse V. Karlsen
Surely this is equivalent to using a built-in sort function.
Paul Johnson
It doesn't use a sort. It relies on the inputs being sorted. It uses a heap though.
recursive
I really don't care if people vote this down. "Code Golf" is a "Do something within these specific boundaries" kinda problem, and the problem was stated as "do not use a sort". If you want to invent new rules, fine by me. It's pure academic either way as nobody would use these self-built "ways".
Lasse V. Karlsen
+5  A: 

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.

haggai_e
+2  A: 

F#: 116 chars:

let p l=
    let f a b=List.filter(a b) in
    let rec s=function[]->[]|x::y->s(f(>)x y)@[x]@s(f(<=)x y) in
    [for a in l->>a]|>s

Note: this code causes F# to throw a lot of warnings, but it works :)

Here's the annotated version with whitespace and meaningful identifiers (note: the code above doesn't use #light syntax, the code below does):

let golf l=
    // filters my list with a specified filter operator
    // uses built-in F# function
    // ('a -> 'b -> bool) -> 'a -> ('b list -> 'b list)
    let filter a b = List.filter(a b)

    // quicksort algorithm
    // ('a list -> 'a list)
    let rec qsort =function
        | []->[]
        | x :: y -> qsort ( filter (>) x y) @ [x] @ qsort ( filter (<=) x y)

    // flattens list
    [for a in l ->> a ] |> qsort
Juliet
I'll post this as a comment rather than a submission, but the absolute shortest version of this code is "let m l=sort(reduce(@)l)", 24 chars, assuming you've opened the Seq module.
Juliet
@Princess, isn't that violating the "no sort built-in" rule?
Alabaster Codify
@Alabaster: I've rolled my own sort without relying on F#'s built-in sort
Juliet
+2  A: 

Though I have not had the patience to try this, a colleague of mine showed me a way that it may be possible to do this using 0 character key - Whie Space

bobwah
+7  A: 

Ruby: 100 characters (1 significant whitespace, 4 significant newlines)

def m(i)
  a=[]
  i.each{|s|s.each{|n|a.insert((a.index(a.select{|j|j>n}.last)||-1)+1,n)}}
  a.reverse
end

Human version:

def sorted_join(numbers)
  sorted_numbers=[]

  numbers.each do |sub_numbers|
    sub_numbers.each do |number|
      bigger_than_me = sorted_numbers.select { |i| i > number }
      if bigger_than_me.last
        pos = sorted_numbers.index(bigger_than_me.last) + 1
      else
        pos = 0
      end

      sorted_numbers.insert(pos, number)
    end
  end

  sorted_numbers.reverse
end

This can all just be replaced by numbers.flatten.sort

Benchmarks:

 a = [[1, 4, 7], [2, 4, 8], [3, 6, 9]]
 n = 50000
 Benchmark.bm do |b|
   b.report { n.times { m(a) } }
   b.report { n.times { a.flatten.sort } }
 end

Produces:

      user     system      total        real
 2.940000   0.380000   3.320000 (  7.573263)
 0.380000   0.000000   0.380000 (  0.892291)

So my algorithm performs horribly, yey!

Samuel
Hate to rain on your parade but there is something fishy going on: m([[2,3,6],[4,7,9],[1,5]])=> [2, 3, 4, 6, 7, 9, 1, 5]
Jonas Elfström
Found the problem, updating...
Samuel
+1 for the thorough work :-)
David Hanak
When I put e.g. m([[1,4,7],[2,4,8],[3,6,9]]) into this I get:=> [1, 2, 4, 3, 4, 6, 7, 8, 9]. Or is that just me?
thesunneversets
+4  A: 

I'll just leave this here...

Language: C, Char count: 265

L[99][99];N;n[99];m[99];i;I;b=0;main(char t){while(scanf("%d%c",L[i]+I,&t)+1){++
I;if(t==10){n[i++]=I;I=0;}}if(I)n[i++] = I;N=i;while(b+1){b=-1;for(i=0;i<N;++i){
I=m[i];if(I-n[i])if(b<0||L[i][I]<L[b][m[b]])b=i;}if(b<0)break;printf("%d ",L[b][
m[b]]);++m[b];}puts("");}

Takes input like such:

1 4 7
2 5 8
3 6 9
(EOF)
strager
Wow. Works for me GCC 4.0.1 on a Mac.
Alabaster Codify
+8  A: 

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))
Svante
+2  A: 

(all other solutions are O(N) (for the input provided))

If we let N be the number of elements in the output and k the number of input lists, then you can't do faster than O(N log k) -- suppose that each list was only a single element, and you'd have faster-than-O(N log N) comparison-based sorting.

Those I've looked at look more like they're O(N*k).

You can fairly easily get down to O(N log k) time: just put the lists in a heap. This is one of the ways to do I/O-efficient sorting (you can generalize quicksort and heaps/heapsort as well).

[no code, just commentary]

Jonas Kölker
A: 

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.

+1  A: 

VB is usually not the language of choice for code golf, but here goes anyway.

The setup -


        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)

        m1.Add(1)
        m1.Add(2)
        m1.Add(3)

        m2.Add(4)
        m2.Add(5)
        m2.Add(6)

        m3.Add(7)
        m3.Add(8)
        m3.Add(9)

        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

An attempt in VB.NET (without sort)

        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While

Another VB.NET attempt (with an allowed sort)


    Private Function Comp(ByVal l1 As List(Of Integer), ByVal l2 As List(Of Integer)) As Integer
        Return l1(0).CompareTo(l2(0))
    End Function
    .
    .
    .
    While m5.Count > 0
        m5.Sort(AddressOf Comp)
        m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        If m5(0).Count = 0 Then m5.RemoveAt(0)
    End While

The entire program -

        Dim rand As New Random
        Dim m1 As List(Of Integer) = New List(Of Integer)
        Dim m2 As List(Of Integer) = New List(Of Integer)
        Dim m3 As List(Of Integer) = New List(Of Integer)
        Dim m4 As List(Of Integer) = New List(Of Integer)
        Dim m5 As List(Of List(Of Integer)) = New List(Of List(Of Integer))
        m5.Add(m1)
        m5.Add(m2)
        m5.Add(m3)

        For Each d As List(Of Integer) In m5
            For i As Integer = 0 To 100000
                d.Add(rand.Next())
            Next
            d.Sort()
        Next

        Dim sw As New Stopwatch
        sw.Start()
        While m5.Count > 0
            Dim idx As Integer = 0
            Dim min As Integer = Integer.MaxValue
            For k As Integer = 0 To m5.Count - 1
                If m5(k)(0) < min Then min = m5(k)(0) : idx = k
            Next
            m4.Add(min) : m5(idx).RemoveAt(0)
            If m5(idx).Count = 0 Then m5.RemoveAt(idx)
        End While
        sw.Stop()

        'Dim sw As New Stopwatch
        'sw.Start()
        'While m5.Count > 0
        '    m5.Sort(AddressOf Comp)
        '    m4.Add(m5(0)(0)) : m5(0).RemoveAt(0)
        '    If m5(0).Count = 0 Then m5.RemoveAt(0)
        'End While
        'sw.Stop()

        Console.WriteLine(sw.Elapsed)
        Console.ReadLine()
Interesting that your "sort" verion is slower than the your first one.
Just a note this uses .NET 2.0.
+1  A: 

Ruby:

41 significant chars, 3 significant whitespace chars in the body of the merge method.

arrs is an array of arrays


  def merge_sort(arrs)
    o = Array.new
    arrs.each do |a|
      o = o | a
    end
    o.sort!
  end

To test in irb:


  arrs = [ [ 90, 4, -2 ], [ 5, 6, -100 ], [ 5, 7, 2 ] ]
  merge_sort(arrs)

Returns: [-100, -2, 2, 4, 5, 6, 7, 90]

Edit: Used the language provided merge/sort because it is likely backed by C code and meets the 'faster' requirement. I'll think about the solution without later (it's the weekend here and I am on holiday).

Adam Hawes
Same interface, 27 chars:def m *l;l.flatten.sort;end
AShelly
+1  A: 

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 });
}
BenAlabaster
A: 

Perl: 22 characters, including two significant whitespace characters.

sub a{sort map{@$_}@_}

Only builtins here. See? ;)

Call like so:

my @sorted = a([1, 2, 3], [5, 6, 89], [13, -1, 3]);
print "@sorted" # prints -1, 1, 1, 2, 3, 3, 5, 6, 89

Honestly, denying language features (note: not libraries...) seems kind-of counter the point. Shortest code to implement in a language should include buildins/language features. Of course, if you import a module, you should count that code against your solution.

Edit: removed unnecessary {}'s around the $_.

Robert P
For the record, the question was posed as such to try and limit people to 1-pass merge sorts, or other novel sort techniques suitable for this special case of input data.
Alabaster Codify
A: 

VB

The setup:

Sub Main()
    f(New Int32() {1, 4, 7}, _
      New Int32() {2, 5, 8}, _
      New Int32() {3, 6, 9})
End Sub

The output:

Sub f(ByVal ParamArray b As Int32()())
    Dim l = New List(Of Int32)
    For Each a In b
        l.AddRange(a)
    Next
    For Each a In l.OrderBy(Function(i) i)
        Console.WriteLine(a)
    Next
End Sub
BenAlabaster
An interesting attempt. However, the rules state that concatenating and sorting aren't allowed.
Adding ranges to a list is effective concatenation.
A: 

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.
Evan Teran
+18  A: 

OCaml in 42 characters:

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

I think I should get extra credit for 42 exactly?

hazzen
+1 for hitting 42 ;)
knittl
A: 

GNU system scripting (I guess that's cheating, but it is nice to know too).

sort -m file1 file2 file3 ...
liori
+2  A: 

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));
Marko Dumic
+1  A: 

F#, 32 chars

let f x=List.sort(List.concat x)

And without using a built in function for the concat (57 chars):

let f x=List.sort(Seq.toList(seq{for l in x do yield!l}))
thr
A: 

BASH in about 250 essential chars

BASH is not really good at list manipulation, anyway this is does the job.

# This merges two lists together
m(){ 
    [[ -z $1 ]] && echo $2 && return; 
    [[ -z $2 ]] && echo $1 && return; 
    A=($1); B=($2); 
    if (( ${A[0]} > ${B[0]} ));then 
        echo -n ${B[0]}\ ;
        unset B[0];
    else 
        echo -n ${A[0]}\ ;
        unset A[0];
    fi;
    m "${A[*]}" "${B[*]}";
}
# This merges multiple lists
M(){
    A=$1;
    shift;
    for x in [email protected]; do
        A=`m "$A" "$x"`
    done
    echo $A
}

$ M '1 4 7' '2 5 8' '3 6 9'
1 2 3 4 5 6 7 8 9
Dan Andreatta
A: 

VB.NET (2008) 185 chars

Accepts List(Of List(Of Byte))

Function s(i)

    s=New List(Of Byte)

    Dim m,c
    Dim N=Nothing

    Do
        m=N
        For Each l In i:
            If l.Count AndAlso(l(0)<m Or m=N)Then m=l(0):c=l

        Next

        If m<>N Then s.Add(m):c.Remove(m)       

    Loop Until m=N

End Function
Anax
A: 

Python, 107 chars:

def f(l):  
 n=[]  
 for t in l:  
  for i in t: n+=[t]  
 s=[]  
 while n: s.+=[min(n)]; n.remove(min(n))  
 return s  
Artur Gaspar