New take on merging. Uses Python's "timsort" to merge in O(n) time.
Python, 8 lines
The usual approach to merging is to loop through both sequences taking the smallest from each until they are both exhausted.
Python's "timsort" detects order in underlying sequences and will run a C speed merge on the data. So, all that is involved is concatenating the sequences and running a sort.
Do not use this approach with other sorts. Most will not detect the underlying order and will run in O(n log n) time.
This approach has other advantages too. This function will detect and correct input sequences that are out of order. Also, Python 2.4's sorted() takes arguments for "reversed" and "key" for customing the sort order and for encapulating the decorate-sort-undecorate pattern. Building these features into the usual merge algorithm takes quite a bit of code and does not run as quickly.