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!

• Keith Randall: Do we have to handle repeated elements within a list, or only between the two lists?
• izzyg: Let's say both. The idea is that you should be able to use this to do merge sort.
• skibrianski: Is it kosher to clobber the input arrays?
• Dennis: 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?
• izzyg: 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.

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

• swish: You can write a%b=a++b after the main pattern matching to handle empty lists, that will shave off couple of characters.
• John Dvorak: doesn't the Haskell solution fail if the first list runs out of content first?
• izzyg: 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.

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

• hlt: In your solutions without generator, use r+=[...] instead of r.append(...) (saves 4 chars every time)
• undergroundmonorail: 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.
• undergroundmonorail: If you split them into different posts I'll upvote the python one.
• Evpok: @undergroundmonorail Do you downvote all the GolfScript answers?
• ɐɔıʇǝɥʇuʎs: @Evpok Now that you mention it, might as well throw it on meta, and see what they have to say there.

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

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

• Dane: 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: I will point out that the question states, "Don't worry about empty lists."
• swish: @Dane The test for emptiness required for recursion to stop.
• algorithmshark: m=:k~`k@.(>&{.)`,@.(0=*&#) saves 2 char.
• algorithmshark: 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 ,.

Answer 6

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]

• swish: Does duplication of arrays in stack makes it O(n^2)?
• Dennis: @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.
• Dennis: 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.
• Dennis: 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.

Answer 7

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.

• izzyg: 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 ...
• xnor: @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: 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)
• Wrzlprmft: @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.
• xnor: @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"?

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

• nderscore: 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]
• Dennis: @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.
• nderscore: Yeah, I'm not sure what the big-o for array->string type conversion is.
• Dennis: 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.
• nderscore: Makes sense. Got it.

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

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 11

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

• Jörg Hülsermann: 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}
• Titus: @JörgHülsermann The array_shift parameter is used by reference. It has to be a variable; an expression won´t work.

Answer 12

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 13

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 14

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}

• user2846289: * 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)=@_}
• skibrianski: @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.

Answer 15

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 16

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)

• Dan Osipov: Exception if a is non empty, but b is empty

Answer 17

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

• izzyg: This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times.
• Wrzlprmft: 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.
• izzyg: Actually, append and extend are implemented differently in python than += is. += creates a new list, while .append and .extend modify an existing one.

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.

• alephalpha: m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b;

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.