Merge two sorted lists

Question

Merge Sort

In this challenge, you will implement the merge subroutine of merge sort. Specifically, you must create a function or program or verb or similar which takes two lists, each sorted in increasing order, and combines them into one list sorted in increasing order. Requirements:

- Your algorithm must take an asymptotically linear amount of time in the size of the input. Please stop giving O(n^2) solutions.

• You may not use any built-in functions capable of sorting a list, or merging a list, or anything like that. Author's discretion.
• The code should be able to handle repeated elements.
• Don't worry about empty lists.

Examples:

merge([1],[0,2,3,4])
[0,1,2,3,4]

merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]

This is code-golf, so may the shortest code win!

Answer 1

Rebmu (35 32 chars)

u[iG^aNXa[rvA]apGtkFaM?fA]apGscA

Test

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[1 5 10 17 19] [2 5 9 11 13 20]] 
== [1 2 5 5 9 10 11 13 17 19 20]

>> rebmu/args [u[iG^aNXa[rvA]apGtkFaM?fA]apGscA] [[2 5 9 11 13 20] [1 5 10 17 19]] 
== [1 2 5 5 9 10 11 13 17 19 20]

About

Rebmu is a dialect of Rebol that permits 'mushing' of regular code for situations that require brevity. Unmushed, the code works somewhat like:

u [                     ; until
    i g^ a nx a [       ; if greater? args next args
       rv a             ; reverse args
    ]                   ; (we want the block containing the next value first)

    ap g tk f a         ; append output take first args
    m? f a              ; empty? first args
]                       ; (first block is now empty)

ap g sc a               ; append output second args
                        ; (add the remainder of the second)

I believe this satisfies the O(n) requirement as the until block is at most looped as many times as the length of the input (and the reverse only switches the order of the container of the input blocks, not the blocks themselves). Using take is perhaps a liberty, but is still a minor efficiency hit.

Rebol (83 75 chars)

Just a wee bit different: in Rebol, paths are a shorter expression than first or second. a is the input block containing the two blocks:

until[if a/2/1 < a/1/1[reverse a]append o:[]take a/1 tail? a/1]append o a/2

Answer 2

OP's solutions:

Haskell 49 44 40

k@(p:r)%l@(q:s)|p>=q=q:k%s|0<1=l%k
a%_=a

Python 131 105 101 99 93

With thanks to @Evpok:

f=lambda u,v:v and(v[-1]<u[-1]and f(v,u)or[b.append(a)for a,b in[(v.pop(),f(u,v))]]and b)or u

Answer 3

Python (79)

from itertools import*
def m(*a):
 while any(a):yield min(compress(a,a)).pop(0)

Python (95, if we're not allowed to return a generator)

from itertools import*
def m(*a):
 r=[]
 while any(a):r+=[min(compress(a,a)).pop(0)]
 return r

Itertools is the solution for all worldy problems.

Bonus: the two of these work on an arbitrary number of lists, and DO worry about empty lists (as in, they'll happily take 2 empty lists, and return an empty list, or take 1 empty and 1 non-empty list, and they'll return the non-empty one. Another added feature of the 2 non-yielded ones: they'll also run with no arguments, and just return an empty list.)

Ungolfed:

from itertools import *  # Import all items from itertools
def m(*a):               # Define the function m, that takes any number of arguments, 
                         #  and stores those arguments in list a
    r=[]                 # Create an empty list r                         
    while any(a):        # While any element in a returns True as value:
        b=compress(a,a)  # Remove any element from a that isn't True (empty lists)
                         #  The example in the official documentation is this one:
                         #  compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
        c=min(b)         # Sort the lists by first value, and take the first one of these.
        d=c.pop(0)       # Take the first element from c
        r.append(d)      # Append this first element to r
    return r             # Gives back r

Answer 4

C - 75

This operates on NULL terminated arrays of int *, though it would work equally well for pointers to other types by substituting the appropriate comparison function for **b < **a (e.g., strcmp(*b, *a) < 0).

void m(int**a,int**b,int**c){while(*a||*b)*c++=!*a||*b&&**b<**a?*b++:*a++;}

Ungolfed:

void merge(int **a, int **b, int **c)
{
    while(*a || *b)
        *c++ = !*a || *b && **b < **a
            ? *b++
            : *a++;
}

Answer 5

Golfscript, 29 27 30 29 26 bytes

~{[email protected]=@<{}{\}if(@@.}do;~]p

or

~{[email protected]=@>{\}*(@@.}do;~]p

How it works

The command

golfscript merge.gs <<< '[2 3] [1 4]'

will get processed as follows:

~            # Interpret the input string.
             #
             # STACK: [2 3] [1 4]
{            #
    .@=0.@=0 # Duplicate the two topmost arrays of the stack and extract their first 
             # elements. This reverses the original order of the first copy.
             #
             # STACK: [1 4] [2 3] 2 1
             #
    >        # Check if the respective first elements of the arrays are ordered.
             #
             # STACK: [1 4] [2 3] 1
             #
    {\}*     # If they are not, swap the arrays. This brings the array with the smallest
             # element to the top of the stack.
             #
             # STACK: [2 3] [1 4]
             #
    (@@      # Shift the first element of the array on top of the stack and rotate it
             # behind the arrays.
             #
             # STACK: 1 [2 3] [4]
             #
    .        # Duplicate the topmost array.
             #
             # STACK: 1 [2 3] [4] [4]
             #
}do          # Repeat this process if the array is non-empty.
             #
             # STACK: 1 [2 3] [4] -> 1 2 [4] [3] -> 1 2 3 [4] []
             #
;~           # Delete the empty array from the stack and dump the non-empty array.
             #
             # STACK: 1 2 3 4
             #
]p           # Combine all elements on the stack into a single array, the to a string and
             # print.

The output is:

[1 2 3 4]

Answer 6

Python (63)(69)(71)

def m(a,b):
 if a[0]>b[0]:a,b=b,a
 return[a.pop(0)]+(m(a,b)if a else b)

I wrote this before seeing OP's comments on runtimes of other answers, so this is another solution that's O(n) in algorithm but not implementation.

Answer 7

J - 42 33

Modified version from here + the comment of @algorithmshark

k=:(m}.),~0{]
m=:k~`k@.(>&{.) ::,

k prepends the head of the right array to the merged tails of both arrays. k~ is the same, but with arrays flipped. (>&{.) is comparing the heads. The code will throw an error if one of the arrays is empty, in that case we return just their concatenation ,.

Answer 8

JavaScript (ES6), 69 79 bytes

f=(a,b,c=[])=>(x=a[0]<b[0]?a:b).length?f(a,b,c.concat(x.shift())):c.concat(a,b)

How it works

f = (a, b, c = []) =>          // `f' is a function that takes arguments `a', `b' and `c' -
                               // `c' defaults to `[]' - which returns the following
                               // expression:
                               //
 (x = a[0] < b[0] ? a : b)     // Store the array among `a' and `b' with the smaller first 
                               // element in `x'.
                               //
 .length ?                     // If it's non-empty,
                               //
  f(a, b, c.concat(x.shift())) // append the first element of array `x' to array `c' and run
                               // `f' again;
                               //
  : c.concat(a,b)              // otherwise, append the arrays `a' and `b' to `c'.
                               //
)

Answer 9

Haskell, 35 bytes

a#b@(c:d)|a<[c]=b#a|0<1=c:a#d
a#_=a

Haskell, 30 bytes (non-competing)

This non-competing version only guarantees linear runtime if a and b have disjoint elements; otherwise it still runs correctly but may use quadratic time.

a#b|a<b=b#a|c:d<-b=c:a#d
a#_=a

Answer 10

PHP 91 98 91 bytes

edit #1: Empty $b requires an addional condition in the curly braces (+7).
edit #2: minor golfings
edit #3: added second version

pretty straight forward. The nicest part is the ternary inside the array_shift
(which fails if you try it without the curlys)

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a&(!$b|$a[0]<$b[0])?a:b});return$c;}

or

function m($a,$b){for($c=[];$a|$b;)$c[]=array_shift(${$a?!$b|$a[0]<$b[0]?a:b:b});return$c;}

ungolfed

function m($a,$b)
{
    $c=[];
    while($a||$b)
    {
        $c[] = array_shift(${
            $a&&(!$b||$a[0]<$b[0])
                ?a
                :b
        });
#       echo '<br>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    }
    return $c;
}

test

$cases = array (
    [1],[0,2,3,4], [0,1,2,3,4],
    [1,5,10,17,19],[2,5,9,11,13,20], [1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20],
    [1,2,3],[], [1,2,3],
    [],[4,5,6], [4,5,6],
);
function outA($a) { return '['. implode(',',$a). ']'; }
echo '<table border=1><tr><th>A</th><th>B</th><th>expected</th><th>actual result</th></tr>';
while ($cases)
{
    $a = array_shift($cases);
    $b = array_shift($cases);
#   echo '<hr>', outA($a), ' / ', outA($b) , ' -> ', outA($c);
    $expect = array_shift($cases);
    $result=m($a,$b);
    echo '<tr><td>',outA($a),'</td><td>',outA($b),'</td><td>', outA($expect), '</td><td>', outA($result),'</td></tr>';
}
echo '</table>';

Answer 11

Go, 124 chars

func m(a,b[]int)(r[]int){for len(a)>0{if len(b)==0||a[0]>b[0]{a,b=b,a}else{r=append(r,a[0]);a=a[1:]}};return append(r,b...)}

Answer 12

JavaScript - 133

function m(a,b){c=[];for(i=j=0;i<a.length&j<b.length;)c.push(a[i]<b[j]?a[i++]:b[j++]);return c.concat(a.slice(i)).concat(b.slice(j))}

Same sort of approach as OP's.

Answer 13

perl, 87 chars / perl 5.14, 78+1=79 chars

This implementation clobbers the input array references. Other than that, it's pretty straight-forward: while both arrays have something, shift off the lower of the two. Then return the merged bit joined with any remaining bits (only one of @$x or @$y will remain). Straight-up perl5, 87 chars:

sub M{($x,$y,@o)=@_;push@o,$$x[0]>$$y[0]?shift@$y:shift@$x while@$x&&@$y;@o,@$x,@$y}

Using perl 5.14.0 and its newfangled arrayref shift: 78 chars + 1 char penalty = 79 chars:

sub M{($x,$y,@o)=@_;push@o,shift($$x[0]>$$y[0]?$y:$x)while@$x&&@$y;@o,@$x,@$y}

Answer 14

Java: 144

This is pretty straightforward. A function that takes two arrays and returns one, the merged version, golfed and without compilation wrapper:

int[]m(int[]a,int[]b){int A=a.length,B=b.length,i,j;int[]c=new int[A+B];for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);return c;}

Ungolfed (with compile-able and runnable wrapper):

class M{
    public static void main(String[]args){
        int[]a=new int[args[0].split(",").length];
        int i=0;
        for(String arg:args[0].split(","))
            a[i++]=Integer.valueOf(arg);
        int[]b=new int[args[1].split(",").length];
        int j=0;
        for(String arg:args[1].split(","))
            b[j++]=Integer.valueOf(arg);
        int[]c=(new M()).m(a,b);
        for(int d:c)
            System.out.printf(" %d",d);
        System.out.println();
    }
    int[]m(int[]a,int[]b){
        int A=a.length,B=b.length,i,j;
        int[]c=new int[A+B];
        for(i=j=0;i+j<A+B;c[i+j]=j==B||i<A&&a[i]<b[j]?a[i++]:b[j++]);
        return c;
    }
}

Example executions:

$ javac M.java
$ java M 10,11,12 0,1,2,20,30
 0 1 2 10 11 12 20 30
$ java M 10,11,12,25,26 0,1,2,20,30
 0 1 2 10 11 12 20 25 26 30

Any tips to shorten would be appreciated.

Answer 15

Scala, 97 bytes

Recursive solution with O(n). To shorten the code, sometimes an operation is done by switching the 2 interchangeable parameters, i.e. f(a,b) calls f(b,a).

type L=List[Int];def f(a:L,b:L):L=if(a==Nil)b else if(a(0)<=b(0))a(0)::f(a.drop(1),b) else f(b,a)

Ungolfed:

type L=List[Int]

def f(a:L, b:L) : L =
  if (a == Nil)
    b 
  else 
    if (a(0) <= b(0))
      a(0) :: f(a.drop(1), b) 
    else
      f(b,a)

Answer 16

APL (32)

{⍺⍵∊⍨⊂⍬:⍺,⍵⋄g[⍋g←⊃¨⍺⍵],⊃∇/1↓¨⍺⍵}

Explanation:

{⍺⍵∊⍨⊂⍬                               if one or both of the arrays are empty
        :⍺,⍵                           then return the concatenation of the arrays
             ⋄g[⍋g←⊃¨⍺⍵]              otherwise return the sorted first elements of both arrays
                          ,⊃∇/        followed by the result of running the function with
                               1↓¨⍺⍵}  both arrays minus their first element

Answer 17

LISP, 117 bytes

The algorithm ends in n + 1 iterations, where n is the length of the shortest list in input.

(defun o(a b)(let((c(car a))(d(car b)))(if(null a)b(if(null b)a(if(< c d)(cons c(o(cdr a)b))(cons d(o a(cdr b))))))))

Answer 18

PYG (50)

def m(*a):
 while An(a):yield Mn(ItCo(a,a)).pop(0)

PYG (64, again, if no generators are allowed.):

def m(*a):
 r=[]
 while An(a):r+=[(Mn(ItCo(a,a)).pop(0)]
 return r

An adaptation of my Python answer.

Answer 19

Python – 69 bytes

def m(A,B):
    C=[]
    while A and B:C+=[[A,B][A>B].pop(0)]
    return C+A+B

If the order of input and output were descending, this could be shortened to 61 bytes:

def m(A,B):
    C=[]
    while A+B:C+=[[A,B][A<B].pop(0)]
    return C

And further down to 45 bytes if generators are allowed:

def m(A,B):
    while A+B:yield[A,B][A<B].pop(0)

Answer 20

Perl 6: 53 characters

sub M(\a,\b){{shift a[0]>b[0]??b!!a}...{a^b},a[],b[]}

Shift from whichever of a or b has the smaller value, until a XOR b (a^b) is true. Then return whatever is left, flattening ([]) the arrays into the list (a[],b[]).

Assuming shifting from the start of an array is O(n), the worst case is two comparisons and one shift per element, so the algorithm is O(n).

Answer 21

JavaScript (ES5) 90 86 90 bytes

function f(a,b){for(o=[];(x=a[0]<b[0]?a:b).length;)o.push(x.shift());return o.concat(a,b)}

edit: (90 - >86) Moved the ternary into the for loop condition. Idea stolen from Dennis.

edit: (86 -> 90) Removed Array to String cast, as it breaks the O(n) requirement.

Answer 22

Mathematica, 137 135

m[a_,b_]:=(l=a;Do[Do[If[b[[f]]<=l[[s]],(l=Insert[l,b[[f]],s];Break[]),If[s==Length@l,l=l~Append~b[[f]]]],{s,Length@l}],{f,Length@b}];l)

Input:

m[{2,2,4,6,7,11},{1,2,3,3,3,3,7}]

Output:

{1, 2, 2, 2, 3, 3, 3, 3, 4, 6, 7, 7, 11}

Ungolfed:

mergeList[a_, b_] := (
    list = a;
    Do[
        Do[(
            If[
                b[[f]] <= list[[s]],
                (list = Insert[list, b[[f]], s]; Break[]),
                If[
                    s == Length@list,
                    list = list~Append~b[[f]]
                ]
        ]),
        {s, Length@list}
    ],
    {f, Length@b}
    ];
    list
)

Could probably do better.

Answer 23

R, 80

Same solution as in Scala and other languages. I am not so sure about x[-1] is O(1).

f=function(a,b)if(length(a)){if(a[1]<=b[1])c(a[1],f(a[-1],b))else f(b,a)}else b

Answer 24

Mathematica, 104 bytes

Reap[{m,n}=Length/@{##};i=k=1;Do[If[k>n||TrueQ[#[[i]]<#2[[k]]],Sow@#[[i++]],Sow@#2[[k++]]],n+m]][[2,1]]&

Anonymous function, stores the length of the two input lists in the variables m and n, then each iteration of the Do loop Sows an element of one the lists incrementing the counter for that list (i for the first, k for the second) by one. If one of the counters exceeds the length of the list, the If statement will always Sow the element from the other list. After n+m operations, all the elements have been taken care of. Reap or rather part [[2,1]] of its output is a list of elements in the order they have been Sown.

I'm not sure of the internals (is accessing a part of a list a O(1) operation or not), but timings looked quite linear on my machine with respect to input list length.