11
1
This is a code-golf question.
Input
A list of non-negative integers in whatever format is the most convenient.
Output
The same list in sorted order in whatever format is the most convenient.
Restriction
- Your code must run in O(n log n) time in the worst case where
n
is the number of integers in the input. This means that randomized quicksort is out for example. However there are many many other options to choose from. - Don't use any sorting library/function/similar. Also don't use anything that does most of the sorting work for you like a heap library. Basically, whatever you implement, implement it from scratch.
You can define a function if you like but then please show an example of it in a full program actually working. It should run successfully and quickly on all the test cases below.
Test cases
In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]
In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]
In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324, 667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]
Your answers
Please state the sorting algorithm you have implemented and the length of your solution in the title of your answer.
O(n log n) time sorting algorithms
There are many O(n log n) time algorithms in existence. This table has a list of some of them.
Some set functions such as
intersect
automatically sort the array. I guess you want to rules those out too. How aboutunique
(remove duplicates, sorts the result)? – Luis Mendo – 2016-03-22T17:42:31.427@DonMuesli I do .. I think
intersect
comes under "similar" if it automatically sorts the array. If you remove duplicates you will give the wrong output. – None – 2016-03-22T17:47:56.143About giving wrong input, leave that to me :-) Could then "remove duplicates and sort" be used? – Luis Mendo – 2016-03-22T17:50:33.290
Can we assume the input will have length > 1? – Alex A. – 2016-03-22T17:52:09.160
@AlexA. Yes absolutely. – None – 2016-03-22T17:56:13.470
@DonMuesli Hmm..go on then :) – None – 2016-03-22T17:56:47.893
Does O(n log n) refer to the algorithm or the implementation? What if we use functions whose implementation we don't know, but we know there's an algorithm for them that runs in O(n log n)? Also, are you sure that "remove duplicates and sort" is allowed? It does the sorting, even if removing duplicates – Luis Mendo – 2016-03-22T18:04:41.580
@DonMuesli No you can't use someone elses code that sorts. Sorry I thought that was clear. I thought you were asking if you could use a unique function that didn't sort. O(n log n) refers to the implementation and the algorithm. You shouldn't use functions whose implementation you don't know. Sorting algorithms are simple and should be implemented from scratch :) – None – 2016-03-22T18:34:44.753
Does this mean that I should prefer e.g.
if(!a)a=[];a.push(e);
toa=[...a||[],e];
because the former has better algorithmic complexity? – Neil – 2016-03-22T21:29:20.4033Nitpick: 0 is not a positive integer. (Under Input) – beaker – 2016-03-22T21:40:57.043
1I like how as soon as the question has anything to do with performance everyone flocks away from the golfing languages even though this is still code-golf and the shortest solution will still win. – Cyoce – 2016-03-26T07:00:07.300