Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question
    
Do we have to handle repeated elements within a list, or only between the two lists? –  Keith Randall Apr 8 at 1:50
    
Let's say both. The idea is that you should be able to use this to do merge sort. –  isaacg Apr 8 at 2:14
    
Is it kosher to clobber the input arrays? –  skibrianski Apr 8 at 3:27
    
Sure, go ahead. –  isaacg Apr 8 at 3:41
1  
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? –  Dennis Apr 9 at 4:06

21 Answers 21

up vote 6 down vote accepted

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
share|improve this answer

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
share|improve this answer
1  
You can write a%b=a++b after the main pattern matching to handle empty lists, that will shave off couple of characters. –  swish Apr 8 at 15:06
    
Thanks for the improvement. –  isaacg Apr 8 at 15:37
    
doesn't the Haskell solution fail if the first list runs out of content first? –  Jan Dvorak Apr 25 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. –  isaacg Apr 25 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
share|improve this answer
    
In your solutions without generator, use r+=[...] instead of r.append(...) (saves 4 chars every time) –  hlt Apr 8 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. –  undergroundmonorail Apr 8 at 12:53
    
If you split them into different posts I'll upvote the python one. –  undergroundmonorail Apr 8 at 12:53
2  
@undergroundmonorail Do you downvote all the GolfScript answers? –  Evpok Apr 8 at 13:20
1  
@Evpok Now that you mention it, might as well throw it on meta, and see what they have to say there. –  ɐɔıʇǝɥʇuʎs Apr 8 at 17:54

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

share|improve this answer
    
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 at 20:02
    
I will point out that the question states, "Don't worry about empty lists." –  Dane Apr 8 at 20:04
    
@Dane The test for emptiness required for recursion to stop. –  swish Apr 8 at 20:21
    
m=:k~`k@.(>&{.)`,@.(0=*&#) saves 2 char. –  algorithmshark Apr 8 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 ,. –  algorithmshark Apr 8 at 21:32

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...)}
share|improve this answer

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.

share|improve this answer

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}
share|improve this answer
    
* 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)=@_} –  VadimR Apr 8 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. –  skibrianski Apr 8 at 19:26

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++;
}
share|improve this answer

Python, 73

Not O(n) and no way to change that without rewriting everything. Still looks cool.

Not optimal, but using a single instruction.

f=lambda u,v:not v and u and(v or u)or(v<u and[v[0]]+f(u,v[1:])or f(v,u))
share|improve this answer
    
Sorry, this is O(n^2), due to the v[:1] step. –  isaacg Apr 8 at 21:17
    
@isaacg According to wiki.python.org/moin/TimeComplexity getting a slice a O(n), am I missing something here? –  Evpok Apr 8 at 21:20
1  
You take that slice a total of n times due to recursion. –  isaacg Apr 8 at 21:22
    
@isaacg Oh, indeed. Thinking of a way to fix it. –  Evpok Apr 8 at 21:27
    
Well, I figured out how to fix it, in a really, really stupid way. Here it is: f=lambda u,v:not v and u and(v or u)or(v[-1]>=u[-1]and[1for a in[v.pop()]]*0+f(u,v)+[a]or f(v,u)) –  isaacg Apr 8 at 21:55

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.

share|improve this answer

Golfscript, 29 27 30 29 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]
share|improve this answer
    
Does duplication of arrays in stack makes it O(n^2)? –  swish Apr 8 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. –  Dennis Apr 8 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. –  Dennis Apr 9 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. –  Dennis Apr 9 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.

share|improve this answer
    
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 ... –  isaacg Apr 10 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 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 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. –  Wrzlprmft Apr 10 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 at 20:43

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.

share|improve this answer

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)
share|improve this answer
    
This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times. –  isaacg Apr 8 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. –  Wrzlprmft Apr 8 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. –  isaacg Apr 8 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).

share|improve this answer

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'.
                               //
)
share|improve this answer
    
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] –  nderscore Apr 9 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. –  Dennis Apr 9 at 18:04
    
Yeah, I'm not sure what the big-o for array->string type conversion is. –  nderscore Apr 9 at 19:54
1  
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. –  Dennis Apr 9 at 19:59
    
Makes sense. Got it. –  nderscore Apr 9 at 20:03

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.

share|improve this answer

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.

share|improve this answer
    
m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b; –  alephalpha Apr 25 at 5:52

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)
share|improve this answer

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
share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.