# 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 , so may the shortest code win!

• Do we have to handle repeated elements within a list, or only between the two lists? Apr 8, 2014 at 1:50
• Let's say both. The idea is that you should be able to use this to do merge sort. Apr 8, 2014 at 2:14
• Is it kosher to clobber the input arrays? Apr 8, 2014 at 3:27
• I'm not sure how to interpret algorithm must take an asymptotically linear amount of time. Algorithms do not take any time, implementations do. The execution time of my Golfscript answer is O(scary) with the Ruby interpreter, but the Online Golfscript Tester behaves much better and could in fact be linear (no real way of telling without the source code though). My point is: b=a;b=b.length might duplicate the entire array a (and result in O(n^2) time if executed for every element) or duplicate just the reference to the array (O(n) time). Which one counts? Apr 9, 2014 at 4:06
• I guess in cases like these, just do your best to figure it out, but if you honestly can't tell, you can assume things work nicely, like the second alternative you mentioned. You can assume that the interpreter works nicely if your language doesn't have a standard interpreter. Apr 9, 2014 at 4:39

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


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


# OP's solutions:

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


# Python 13110510199 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

• You can write a%b=a++b after the main pattern matching to handle empty lists, that will shave off couple of characters. Apr 8, 2014 at 15:06
• doesn't the Haskell solution fail if the first list runs out of content first? Apr 25, 2014 at 6:46
• If you look at the first function, it recursively calls the function with the shortened list as the second argument, and the lengthened list as the first argument, or else swaps the arguments. Therefore, the first argument never gets shorter. Since by the OP it does not start empty, it will never empty. Apr 25, 2014 at 8:29

# 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

• In your solutions without generator, use r+=[...] instead of r.append(...) (saves 4 chars every time)
– hlt
Apr 8, 2014 at 12:40
• I don't mean any offense by this, but if your answer contains code in a language that's just another language with modifications made specifically for golfing, I'm going to downvote it. It's a shame, the real python answers are good. Apr 8, 2014 at 12:53
• If you split them into different posts I'll upvote the python one. Apr 8, 2014 at 12:53
• @undergroundmonorail Do you downvote all the GolfScript answers? Apr 8, 2014 at 13:20
• @Evpok Now that you mention it, might as well throw it on meta, and see what they have to say there. Apr 8, 2014 at 17:54

# 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++;
}


# Golfscript, 29273029 26 bytes

~{.0=@.0=@<{}{\}if(@@.}do;~]p


or

~{.0=@.0=@>{\}*(@@.}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]

• Does duplication of arrays in stack makes it O(n^2)? Apr 8, 2014 at 20:45
• @swish: I'm no computer scientist, but I'd say it depends on the implementation. If the interpreter actually duplicates the entire arrays, I guess it does. Apr 8, 2014 at 21:17
• The previous version was O(n^2) for very similar arrays (e. g., [1 1 1 ... 2] and [1 1 1 ... 3]), since comparing the arrays (rather than their first elements) would be very slow in this case. Apr 9, 2014 at 18:53
• The only array operations that take place in the new version are duplication, swapping and rotation on the stack. Since the duplicated arrays are only used to extract single elements and test the arrays for non-emptiness (both destructive operations in Golfscript), the above code can be run in O(n) time (by duplicating, swapping and rotating the references to the arrays). Actual performance depends on the interpreter. Apr 9, 2014 at 18:54

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

• What algorithms have extracts from the front of arrays as O(1)? What algorithms have list comparisons take O(1)? Also, you can golf it further by changing ... if ... else ... to ... and ... or ... Apr 10, 2014 at 8:18
• @isaacg Shoot, I'd forgotten about repetitions possibly making the list comparison O(n). So, I've taken out that optimization for 6 more characters. You can extract from and append to the front in O(1) in a linked list. I don't see how you can make ...and...or... play nice with returning the value.
– xnor
Apr 10, 2014 at 18:28
• OK, I see now how to do ...and...or..., but it doesn't save chars due to the parens needed. return[a.pop(0)]+(a and m(a,b)or b)
– xnor
Apr 10, 2014 at 19:01
• @isaacg: To extract the front of an array in O(1), just increase the array pointer such that it points to the second element and release the memory consumed by the first element. Apr 10, 2014 at 19:35
• @Wrzlprmft I couldn't get the array trick to work because both elements of the array are evaluated regardless of the boolean value, which throws an error when a is the empty list. Is there a short way to make a "lazy array"?
– xnor
Apr 10, 2014 at 20:43

## 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 ,.

• I'm presuming that since /:~ a,b is the forbidden answer (along with [:/:~,), that you're shooting for the shortest answer that does not include /:, right?
– Dane
Apr 8, 2014 at 20:02
• I will point out that the question states, "Don't worry about empty lists."
– Dane
Apr 8, 2014 at 20:04
• @Dane The test for emptiness required for recursion to stop. Apr 8, 2014 at 20:21
• m=:k~k@.(>&{.),@.(0=*&#) saves 2 char. Apr 8, 2014 at 21:07
• In fact, you can get the whole thing down to 33 char: k=:(m}.),~0{] and m=:k~k@.(>&{.) ::,. We use 0{ to throw an error when the list is empty, and then catch that error and exit with ,. Apr 8, 2014 at 21:32

# 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'.
//
)

• Comparing the arrays with the < operator isn't valid as it does a string comparison: f([123, 456, 789], [1, 2, 3, 4, 5]) => [1, 123, 2, 3, 4, 456, 5, 789] Apr 9, 2014 at 16:44
• @nderscore: Right. It wouldn't have worked anyway, since comparing the whole arrays might not be O(n). The same seems to be true for the non-emptiness test, which has to convert the entire array to a string. Apr 9, 2014 at 18:04
• Yeah, I'm not sure what the big-o for array->string type conversion is. Apr 9, 2014 at 19:54
• Concatenating an array with [] and then converting it into a string requires O(n) time. Doing so once for all n elements of the array takes O(n^2) time. Apr 9, 2014 at 19:59
• Makes sense. Got it. Apr 9, 2014 at 20:03

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


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


# 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>';

• I could not understand why you make it not simple $a&(!$b|$a[0]<$b[0])?$a:$binstead of ${$a&(!$b|$a[0]<$b[0])?a:b} Apr 11, 2017 at 14:45 • @JörgHülsermann The array_shift parameter is used by reference. It has to be a variable; an expression won´t work. Apr 12, 2017 at 8:27 ## 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...)}  # 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. # 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}  • * instead of && will save a byte. And even more if sub M{map{shift(!@$x+@$y*($$y[0]<$$x[0])?$y:$x)}map@$_,($x,$y)=@_} Apr 8, 2014 at 16:55
• @VadimR, wow. nice work. Go ahead and post that if you like - I never would have thought to do the double map trick instead of pushing on an array. Apr 8, 2014 at 19:26

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

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

• Exception if a is non empty, but b is empty Nov 6, 2014 at 22:44

## 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


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


# 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


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

• This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times. Apr 8, 2014 at 21:24
• I didn’t even know until now that lists aren’t implemented as lists in Python and even then pop(0) can be implemented in O(1) and += can at least be implemented better than O(n) (see the link). By the way, your solution uses += (i.e., append and extend) as often as mine. Anyway, all that is an implementation question (as far as I know), so in a (fictional) Python implementation, where lists are implemented as lists, my function is O(n). Finally your question required the algorithm to be O(n), and mine is. Apr 8, 2014 at 22:53
• Actually, append and extend are implemented differently in python than += is. += creates a new list, while .append and .extend modify an existing one. Apr 8, 2014 at 23:38

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

# JavaScript (ES5) 9086 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.

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

• m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b; Apr 25, 2014 at 5:52

# 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


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