14
4
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!
Do we have to handle repeated elements within a list, or only between the two lists? – Keith Randall – 2014-04-08T01:50:33.423
Let's say both. The idea is that you should be able to use this to do merge sort. – isaacg – 2014-04-08T02:14:13.940
Is it kosher to clobber the input arrays? – skibrianski – 2014-04-08T03:27:09.993
Sure, go ahead. – isaacg – 2014-04-08T03:41:50.290
Hmm, would using
min
comply to the rules? – ɐɔıʇǝɥʇuʎs – 2014-04-08T12:15:24.117Solutions using min are unlikely to be O(n). However, if you can do it, go ahead. – isaacg – 2014-04-08T15:34:15.203
About the output: 1. A program will necessarily output a string. Does it matter how the list elements are separated (spaces, newlines, etc.)? 2. Does a function have to output an array or can it output something else (string, elements ordered on the stack, etc.) as well? – Dennis – 2014-04-08T20:43:36.490
Anything with the right informational content is fine. In other words, all of the above. – isaacg – 2014-04-08T21:09:08.370
Can we assume that the elements will be non-negative integers? – Dennis – 2014-04-09T00:41:41.487
@Dennis No. All you can assume is that they are comparable by > and the like. – isaacg – 2014-04-09T00:58:17.933
3
I'm not sure how to interpret algorithm must take an asymptotically linear amount of time. Algorithms do not take any time, implementations do. The execution time of my Golfscript answer is O(scary) with the Ruby interpreter, but the Online Golfscript Tester behaves much better and could in fact be linear (no real way of telling without the source code though). My point is:
– Dennis – 2014-04-09T04:06:41.633b=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?1I guess in cases like these, just do your best to figure it out, but if you honestly can't tell, you can assume things work nicely, like the second alternative you mentioned. You can assume that the interpreter works nicely if your language doesn't have a standard interpreter. – isaacg – 2014-04-09T04:39:09.473