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.
merge(,[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!