# 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)? – Luis Mendo Mar 22 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. – Lembik Mar 22 at 17:47
About giving wrong input, leave that to me :-) Could then "remove duplicates and sort" be used? – Luis Mendo Mar 22 at 17:50
Nitpick: 0 is not a positive integer. (Under Input) – beaker Mar 22 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. – Cyoce Mar 26 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. – proud haskeller Mar 22 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 Mar 22 at 19:04
@nimi Right, thanks! – proud haskeller Mar 22 at 19:05
You are the winner! The only answer using fewer bytes didn't run in O(n log n). – Lembik Mar 30 at 13:41
It is now it seems :) – Lembik Mar 31 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)}

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

-
Thank you for the non mergesort answer! – Lembik Mar 23 at 13:22
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 – proud haskeller Mar 23 at 15:48
@proudhaskeller Ah yes.. i just looked up stackoverflow.com/a/2186785/2179021 . – Lembik Mar 23 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). – Lembik Mar 23 at 14:36
To be clear, this means that the 132 version is OK but the 99 byte version is non-complying. – Lembik Mar 24 at 19:04

# 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 :) – Lembik Mar 22 at 19:21
@Lembik I think Sp3000 and Doorknob are our resident Nim and Rust experts, respectively. Hopefully they join the fun too. ;) – Alex A. Mar 22 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:

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!)

-

# 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. – Lembik Mar 23 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 Mar 23 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? – Lembik Mar 23 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 Mar 23 at 21:34
Jelly is implemented in Python and is implemented as .pop(0). – Lynn Mar 23 at 21:34

# 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? – Lembik Mar 22 at 18:35
I added a link so you can test it. – Kevin Lau - not Kenny Mar 22 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.