11
\$\begingroup\$

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]

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.

\$\endgroup\$
  • \$\begingroup\$ 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)? \$\endgroup\$ – Luis Mendo Mar 22 '16 at 17:42
  • \$\begingroup\$ @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. \$\endgroup\$ – user9206 Mar 22 '16 at 17:47
  • \$\begingroup\$ About giving wrong input, leave that to me :-) Could then "remove duplicates and sort" be used? \$\endgroup\$ – Luis Mendo Mar 22 '16 at 17:50
  • 3
    \$\begingroup\$ Nitpick: 0 is not a positive integer. (Under Input) \$\endgroup\$ – beaker Mar 22 '16 at 21:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Cyoce Mar 26 '16 at 7:00
8
\$\begingroup\$

Haskell, 87 80 89

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – proud haskeller Mar 22 '16 at 19:03
  • \$\begingroup\$ 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. \$\endgroup\$ – nimi Mar 22 '16 at 19:04
  • \$\begingroup\$ You are the winner! The only answer using fewer bytes didn't run in O(n log n). \$\endgroup\$ – user9206 Mar 30 '16 at 13:41
  • \$\begingroup\$ @Lembik Right, I forgot the Jelly answer didn't comply. \$\endgroup\$ – proud haskeller Mar 30 '16 at 19:08
  • 1
    \$\begingroup\$ It is now it seems :) \$\endgroup\$ – user9206 Mar 31 '16 at 6:16
5
\$\begingroup\$

JavaScript (ES6), 195 193 191 189 188 186 183 182 179 174 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>

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – proud haskeller Mar 23 '16 at 15:48
  • \$\begingroup\$ @proudhaskeller Ah yes.. i just looked up stackoverflow.com/a/2186785/2179021 . \$\endgroup\$ – user9206 Mar 23 '16 at 15:59
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thank you for this. I definitely meant the algorithm and implementation should be O(n log n). \$\endgroup\$ – user9206 Mar 23 '16 at 14:36
  • \$\begingroup\$ To be clear, this means that the 132 version is OK but the 99 byte version is non-complying. \$\endgroup\$ – user9206 Mar 24 '16 at 19:04
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Good to see Julia here. Now we need nim and rust too :) \$\endgroup\$ – user9206 Mar 22 '16 at 19:21
  • 1
    \$\begingroup\$ @Lembik I think Sp3000 and Doorknob are our resident Nim and Rust experts, respectively. Hopefully they join the fun too. ;) \$\endgroup\$ – Alex A. Mar 22 '16 at 19:29
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

Attribution:

\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Would you mind adding some explanation please. \$\endgroup\$ – user9206 Mar 23 '16 at 15:57
  • \$\begingroup\$ There’s a lot to explain :) Let me see if I can golf down the last line a tiny bit more \$\endgroup\$ – Lynn Mar 23 '16 at 16:01
  • \$\begingroup\$ 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? \$\endgroup\$ – user9206 Mar 23 '16 at 20:05
  • \$\begingroup\$ 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). \$\endgroup\$ – Lynn Mar 23 '16 at 21:34
  • \$\begingroup\$ Jelly is implemented in Python and is implemented as .pop(0). \$\endgroup\$ – Lynn Mar 23 '16 at 21:34
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thank you for this! Can you show it working too? \$\endgroup\$ – user9206 Mar 22 '16 at 18:35
  • 1
    \$\begingroup\$ I added a link so you can test it. \$\endgroup\$ – Value Ink Mar 22 '16 at 18:47
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – proud haskeller Mar 22 '16 at 23:22
  • \$\begingroup\$ 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 \$\endgroup\$ – Value Ink Mar 23 '16 at 2:27
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – daniero Mar 23 '16 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy