# A classic sorting code-golf question

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 nis 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]

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 about unique (remove duplicates, sorts the result)? Commented Mar 22, 2016 at 17:42
• @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.
– user9206
Commented Mar 22, 2016 at 17:47
• About giving wrong input, leave that to me :-) Could then "remove duplicates and sort" be used? Commented Mar 22, 2016 at 17:50
• Nitpick: 0 is not a positive integer. (Under Input) Commented Mar 22, 2016 at 21:40
• I 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. Commented Mar 26, 2016 at 7:00

s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s s=r.map(:[]) This is merge sort, implemented from the bottom up. first we package every element into it's own list, and then merge them two-by-two, and again merge them two-by-two, until we're left with one list. (%) is the merge function j merges pairs in a list of lists r merges a complete list of lists s is the sorting function. Usage: Run an interpreter, and enter s [3,5,2,6,7]. Edit: the way I was merging things before wasn't the right order, So to fix it I needed 9 more characters. • @Lembik if you want to test the program, and you don't want to install Haskell, you can use ideone, and add a line like main = print (s [5,3,6,8]), which will set main to printing the result of the sorting. Commented Mar 22, 2016 at 19:03 • I think you don't need []%s=s, because if the first element is [], the (x:a) match fails and the last case flips the elements, so that s%[] succeeds. – nimi Commented Mar 22, 2016 at 19:04 • You are the winner! The only answer using fewer bytes didn't run in O(n log n). – user9206 Commented Mar 30, 2016 at 13:41 • @Lembik Right, I forgot the Jelly answer didn't comply. Commented Mar 30, 2016 at 19:08 • It is now it seems :) – user9206 Commented Mar 31, 2016 at 6:16 # JavaScript (ES6), 195193191189188186183182179174 172 bytes This is a heapsort implementation. I expect someone to come up with a shorter mergesort, but I like this one :P Update: R mergesort beaten. Ruby up next :D S=l=>{e=l.length W=(a,b)=>[l[a],l[b]]=[l[b],l[a]] D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)} for(s=e>>1;s;)D(--s) for(;--e;D(0))W(0,e)} ### Test (Firefox) S=l=>{e=l.length W=(a,b)=>[l[a],l[b]]=[l[b],l[a]] D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)} for(s=e>>1;s;)D(--s) for(;--e;D(0))W(0,e)} document.querySelector('#d').addEventListener("click",function(){a=JSON.parse(document.querySelector('#a').value);S(a);document.querySelector('#b').innerHTML=JSON.stringify(a)}); <textarea id="a">[9,4,1,2,7,3,5,8,6,10]</textarea><br><button id="d">Sort</button><br><pre id="b"></pre> • I would have loved to write a heapsort answer, but it doesn't really work well with Haskell. My next try would be JS, but you've done it. Maybe I will still do that though. Idk Commented Mar 23, 2016 at 15:48 • @proudhaskeller Ah yes.. i just looked up stackoverflow.com/a/2186785/2179021 . – user9206 Commented Mar 23, 2016 at 15:59 # Python3, 132 bytes def S(l): if len(l)<2:return l a,b,o=S(l[::2]),S(l[1::2]),[] while a and b:o.append([a,b][a[-1]<b[-1]].pop()) return a+b+o[::-1] Simple mergesort. Lots of bytes were spent to make sure this actually runs in O(n log n), if only the algorithm, but not the implementation needs to be O(n log n), this can be shortened: # Python3, 99 bytes def m(a,b): while a+b:yield[a,b][a<b].pop(0) S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l This is not O(n log n) because .pop(0) is O(n), making the merge function O(n^2). But this is fairly artificial, as .pop(0) could easily have been O(1). • Thank you for this. I definitely meant the algorithm and implementation should be O(n log n). – user9206 Commented Mar 23, 2016 at 14:36 • To be clear, this means that the 132 version is OK but the 99 byte version is non-complying. – user9206 Commented Mar 24, 2016 at 19:04 • 119 version Commented Mar 1 at 23:02 # Jelly, 29 bytes, merge sort Like orlp’s Python answer, this uses list.pop(0) under the hood, which is O(n), but the implementation is formally O(n log n). ṛð>ṛḢð¡Ḣ;ñ ç;ȧ? s2Zß€ç/µL>1µ¡ Try it here. ## Explanation Define f(x, y): (merge helper) Implicitly store x in α. ṛ ð¡ Replace it with y this many times: ð>ṛḢ (x > y)[0]. Ḣ Pop the first element off that list (either x or y). ;ñ Append it to g(x, y). Define g(x, y): (merge) ȧ? If x and y are non-empty: ç Return f(x, y) Else: ; Return concat(x, y). Define main(z): (merge sort) µL>1µ¡ Repeat (len(z) > 1) times: s2 Split z in chunks of length two. [[9, 7], [1, 3], [2, 8]] Z Transpose the resulting array. [[9, 1, 2], [7, 3, 8]] ß€ Apply main() recursively to each. [[1, 2, 9], [3, 7, 8]] ç/ Apply g on these two elements. [1, 2, 3, 7, 8, 9] • Would you mind adding some explanation please. – user9206 Commented Mar 23, 2016 at 15:57 • There’s a lot to explain :) Let me see if I can golf down the last line a tiny bit more – lynn Commented Mar 23, 2016 at 16:01 • When you say the implementation is O(n log n) but it uses list.pop(0) under the hood, which is O(n) I am confused. What do you mean? – user9206 Commented Mar 23, 2016 at 20:05 • I mean exactly what orlp wrote in his answer: This is not O(n log n) because .pop(0) is O(n), making the merge function O(n^2). But this is fairly artificial, as .pop(0) could easily have been O(1). – lynn Commented Mar 23, 2016 at 21:34 • Jelly is implemented in Python and is implemented as .pop(0). – lynn Commented Mar 23, 2016 at 21:34 # Julia, 166 bytes m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])] M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x The primary function is called M and it calls a helper function m. It uses merge sort, which has O(n log n) as its worst case complexity. Example use: x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0] println(M(x)) # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] println(M(x) == sort(x)) # prints true Ungolfed: function m(a, b, i=1, k=1, L=endof) return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ? a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])] end function M(x, n=endof(x)) q = ceil(Int, n÷2) return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x end • Good to see Julia here. Now we need nim and rust too :) – user9206 Commented Mar 22, 2016 at 19:21 • @Lembik I think Sp3000 and Doorknob are our resident Nim and Rust experts, respectively. Hopefully they join the fun too. ;) Commented Mar 22, 2016 at 19:29 # R, 181 bytes, Mergesort L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)} Indented, with newlines: L=length s=function(S) if(L(S)<2){ S }else{ h=1:(L(S)/2) A=s(S[h]) B=s(S[-h]) Z=c() if(A[L(A)]>B[1]) #Merge helper function incorporated from here ... while(L(A)&L(B)) if(A[1]<B[1]){ Z=c(Z,A[1]) A=A[-1] }else{ Z=c(Z,B[1]) B=B[-1] } #...to here. Following line both finishes merge function and handles 'else' case: c(Z,A,B) } Test cases: > L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)} > s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324, 667269)) [1] 667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622 > s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7)) [1] 1 1 2 2 3 4 6 7 7 9 > s(c(72, 59, 95, 68, 84)) [1] 59 68 72 84 95 > s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0)) [1] 0 1 2 3 4 5 6 7 8 9 ## Scala, 243 Byte function (315 Bytes stand-alone app), Mergesort This answer is intended to be a function, but can be expanded to be a stand-alone application. Function-only (243 bytes): object G{ type S=Stream[Int] def m(f:(S,S)):S=f match{ case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b) case(a,y#::b)=>y#::m(a,b) case(a,Empty)=>a case(_,b)=>b} def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a } Stand-alone application(315 bytes): object G extends App{ type S=Stream[Int] def m(f:(S,S)):S=f match{ case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b) case(a,y#::b)=>y#::m(a,b) case(a,Empty)=>a case(_,b)=>b} def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a println(s(args(0).split(",").map(_.toInt).toStream).toList) } Usage: Function: G.s(List(**[Paste your array here]**).toStream).toList Application: sbt "run **[Paste your array here]**" Example Input: scala> G.s(List(10,2,120,1,8,3).toStream).toList (OR)$ sbt "run 5423,123,24,563,65,2,3,764"

Output:

res1: List[Int] = List(1, 2, 3, 8, 10, 120)

OR

List(2, 3, 24, 65, 123, 563, 764, 5423)

Constraints & considerations:

• Requires scalaz (very common library, not used for sorting here)
• Is 100% functional (nothing mutable!)

# Ruby, 167 bytes

Golfed merge sort algorithm, which has worst-case O(n log n)

f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

Test it here!

To test, copy and paste the code into the window, and add puts f[x] at the bottom, where x is an array with the input. (Make sure you select Ruby as the language, of course) For example, puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]

• Thank you for this! Can you show it working too?
– user9206
Commented Mar 22, 2016 at 18:35
• I added a link so you can test it. Commented Mar 22, 2016 at 18:47

## Ruby, 297 bytes

Merge sort. Complete program, instead of a function. Requires two arguments at runtime: input file and output file, each with one element per line.

if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end • If it would shorten your code, you should consider adapting the code to being a function which gets an array as an input and returns the sorted sequence. seems it would get you rid of lots of bytes. Commented Mar 22, 2016 at 23:22 • If you're going to keep it as a full program instead of a function, might I suggest using STDIN and STDOUT as input/output, respectively?$stdin.readlines already is fewer bytes than open(ARGV[0]).readlines, same with puts over open(ARGV[1],"w"){|f|f.puts Commented Mar 23, 2016 at 2:27
• And stuff like if \$0==__FILE__ is really unnecessary in a code golf. You might also condiser replacing each ; with a newline -- it's the same byte count and (probably) removes the horizontal scroll of the code. Also, I'll recommend checking out tips for golfing in Ruby. Commented Mar 23, 2016 at 8:49