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

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

Answer 2

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

Answer 3

(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]

Answer 4

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)

Answer 5

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

Answer 6

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