14
\$\begingroup\$

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!

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

24 Answers 24

8
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can write a%b=a++b after the main pattern matching to handle empty lists, that will shave off couple of characters. \$\endgroup\$ – swish Apr 8 '14 at 15:06
  • \$\begingroup\$ doesn't the Haskell solution fail if the first list runs out of content first? \$\endgroup\$ – John Dvorak Apr 25 '14 at 6:46
  • \$\begingroup\$ 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. \$\endgroup\$ – isaacg Apr 25 '14 at 8:29
4
\$\begingroup\$

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

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++;
}
\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Does duplication of arrays in stack makes it O(n^2)? \$\endgroup\$ – swish Apr 8 '14 at 20:45
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Apr 8 '14 at 21:17
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Apr 9 '14 at 18:53
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Apr 9 '14 at 18:54
2
\$\begingroup\$

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

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

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'.
                               //
)
\$\endgroup\$
  • \$\begingroup\$ 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] \$\endgroup\$ – nderscore Apr 9 '14 at 16:44
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Apr 9 '14 at 18:04
  • \$\begingroup\$ Yeah, I'm not sure what the big-o for array->string type conversion is. \$\endgroup\$ – nderscore Apr 9 '14 at 19:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis Apr 9 '14 at 19:59
  • \$\begingroup\$ Makes sense. Got it. \$\endgroup\$ – nderscore Apr 9 '14 at 20:03
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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>';
\$\endgroup\$
  • \$\begingroup\$ 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} \$\endgroup\$ – Jörg Hülsermann Apr 11 '17 at 14:45
  • 1
    \$\begingroup\$ @JörgHülsermann The array_shift parameter is used by reference. It has to be a variable; an expression won´t work. \$\endgroup\$ – Titus Apr 12 '17 at 8:27
1
\$\begingroup\$

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...)}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ * 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)=@_} \$\endgroup\$ – user2846289 Apr 8 '14 at 16:55
  • \$\begingroup\$ @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. \$\endgroup\$ – skibrianski Apr 8 '14 at 19:26
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Exception if a is non empty, but b is empty \$\endgroup\$ – Dan Osipov Nov 6 '14 at 22:44
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 ... \$\endgroup\$ – isaacg Apr 10 '14 at 8:18
  • \$\begingroup\$ @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. \$\endgroup\$ – xnor Apr 10 '14 at 18:28
  • \$\begingroup\$ 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) \$\endgroup\$ – xnor Apr 10 '14 at 19:01
  • \$\begingroup\$ @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. \$\endgroup\$ – Wrzlprmft Apr 10 '14 at 19:35
  • \$\begingroup\$ @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"? \$\endgroup\$ – xnor Apr 10 '14 at 20:43
1
\$\begingroup\$

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))))))))
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times. \$\endgroup\$ – isaacg Apr 8 '14 at 21:24
  • \$\begingroup\$ 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. \$\endgroup\$ – Wrzlprmft Apr 8 '14 at 22:53
  • \$\begingroup\$ Actually, append and extend are implemented differently in python than += is. += creates a new list, while .append and .extend modify an existing one. \$\endgroup\$ – isaacg Apr 8 '14 at 23:38
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b; \$\endgroup\$ – alephalpha Apr 25 '14 at 5:52
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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