Merge two sorted lists 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!
Rebmu (35 32 chars)

u[iG^aNXa[rvA]apGtkFaM?fA]apGscA


Test

&gt;&gt; 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]

&gt;&gt; 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 &lt; a/1/1[reverse a]append o:[]take a/1 tail? a/1]append o a/2