Merge two sorted lists

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

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

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