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!
b=a;b=b.length
might duplicate the entire arraya
(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\$