The Challenge

It's quite simple really, sort a list of numbers.

Details

You must sort a list of numbers in ascending order, without using any built-in sorting functions/libraries/etc (i.e. list.sort() in Python).

Input/output can be done in any method you choose, as long as it is human readable.

Standard loopholes are disallowed as always.

Shortest code in bytes wins.

You must explain/list what sort method you used (Bubble, Insertion, Selection, etc.)

Input will not contain duplicates.

Sample Input/Output

Input: 99,-2,53,4,67,55,23,43,88,-22,36,45

Output: -22,-2,4,23,36,43,45,53,55,67,88,99

Note: A near direct opposite of Sort a List of Numbers

• I'm very surprised if this isn't a duplicate, but I don't have the time to check. Anyway, "built-in sorting functions" should be better defined. Can you use a function that indexes all values? [7 2 4 1] -> [4 2 3 1]. Also, can the CSV list be inside brackets? Also, the specific input format is very suitable for some languages, and bad for others. This makes input parsing a big part for some submissions, and unnecessary for others. – Stewie Griffin Apr 15 '16 at 12:52
• @StewieGriffin I've seen many sorting challenges, but none dealing with sorting just a basic integer list. There are many challenges that are easier for some languages, and much more difficult in others. – Michelfrancis Bustillos Apr 15 '16 at 13:00
• This is very similar, but has a O(Nlog(N)) restriction. – Nathan Merrill Apr 15 '16 at 14:06
• Very closely related to this question, but since some answers here (e.g. Dennis' range filtering) require the input to be integers I won't vote to close as dupe. – Peter Taylor Apr 15 '16 at 20:55
• Relevant: youtube.com/user/AlgoRythmics/videos — An Youtube channel which teaches sorting algorithms through Hungarian dances! – sergiol Apr 30 '17 at 12:05

Python 3, 53 bytes

lambda l:[i for i in range(min(l),max(l)+1)if i in l]


Try it online!

• This is essentially a bucket sort, right? So it fails if the input doesn't fall in the range of the hash table size? Can that happen? – Jakob Aug 28 '17 at 0:02
• @Jakob I don't think so? To me it's just a range between min and max values, filtered with the input list – ASCII-only Aug 28 '17 at 0:14
• @ASCII-only: agreed. Filtering the range between min and max looks like an implementation of en.wikipedia.org/wiki/Counting_sort to me, because it's sort of like making a histogram. (Same as @Mendeleev's Ruby answer) – Peter Cordes Nov 26 '17 at 4:57

R, 47 bytes

implements bogosort.

function(l){while(is.unsorted(l))l=sample(l);l}


Try it online!

Jolf, 13 bytes

Uses bogosort. Try it out here! Replace ⌂ with \x7f. Input is a comma-separated list of numbers like 5,3,2,4,1.

W⌂Z,k)ok Tk}k


Explanation:

W⌂Z,k)ok Tk}k
W    )         while
⌂Z,            !isSorted
k            input {
ok          k =
_Tk        shuffle(k)
}   }
k  out k


Javascript 55 bytes

a=>[...a].map(b=>a.splice(a.indexOf(Math.min(...a)),1)

• Doesn't work for me on Firefox; for the sample input I get [[-22], [-2], [4], [23], [36], [43], , , , , , ,]. – Neil May 19 '16 at 19:33
• @Neil yeah, missed something – Bálint May 19 '16 at 19:44

Python 2, 159

Implements bozosort (randomly swap two elements until the array is sorted).

It's not very efficient...

from random import randint as r
def b(l):
s,a=len(l)-1,0
while not a:
c,d=r(0,s),r(0,s);l[d],l[c]=l[c],l[d];e,a=l[0],1
for f in l:a,e=a*(f>=e),f
return l

• you can save a couple of bytes by indenting s,a=..., while not a: and return l with a single space, and the contents of the while loop with a single tab because tab is considered deeper indentation than space. that will make this answer python2 only, though – undergroundmonorail May 20 '16 at 0:16
• @undergroundmonorail Thanks! – Numeri says Reinstate Monica May 20 '16 at 13:58
• You can probably use while a<1, or if a is always 0 or 1, you can use while~-a – mbomb007 Apr 25 '17 at 20:46

Tcl, 49: sleep sort

The examples so far aren't very consistent in how they take input, so this sorts command-line arguments. On particularly slow systems, where the foreach takes more than a millisecond, it might need three extra bytes (after ${x}0). foreach x$argv {after $x puts$x}
vwait forever


SmileBASIC, 79 bytes

DEF S A
FOR Z=0TO I
FOR I=1TO LEN(A)-1SWAP A[I-(A[I-1]>A[I])],A[I]NEXT
NEXT
END


It's bubble sort but instead of checking to see if it's finished, it just assumes that every input is the worst case and does n^2 (actually n*(n+2)) iterations.

Perl 5, 65 bytes

Insertion sort subroutine:

sub r{map{$t=0;$_[$_]<$_[$t]&&($t=$_)for 0..$#_;splice@_,$t,1}@_}  Try it online! Dodos, 75 bytes  / / / s w w h / t s s R R t h h t I q q dot t dot I I dip t dab  Try it online! Only support non negative integers. Terrible runtime, especially for large numbers. Explanation First, define t to be the tail of a list. (all elements except the first) Given a list [x,y] where x<y, function I computes the incremental difference (with a 0 prepended), which is used in h (head of a list, by getting the sum of all elements, subtract by the sum of all elements except the first) Function R reverses a list of 2 elements. (concatenate the tail and the head) Generally, it rotates the first element to the last. s sorts a list of 2 elements. Generally, given a list, it find the least non negative n such that rotate the list left by n make the list less than itself Red. / sorts a list of arbitrarily many elements, by / the list' tail, and then / s the result. Haskell, 97 bytes s=f.map pure a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b a!b=a++b d(x:y:z)=x!y:d z d p=p f[x]=x f x=f$d x


Try it online!

A stable, incremental merge sort.

C#, 125 bytes

using System.Linq;x=>{for(int i=0;i<x.Count;i++){int temp=x.GetRange(i,x.Count-i).Min();x[x.IndexOf(temp)]=x[i];x[i]=temp;}};


It uses the selection sort. I don't need to return the sorted list, because in C# lists are reference types, so the variable only holds a reference to the actual object, and if I change the object from here, it'll be visible at other places, as described in this stackoverflow question.

Tcl, 160 bytes

set i 0
time {incr j;set x 0;while \$x<$i {if [lindex $L$i]<[lindex $L$x] {set L [lreplace [linsert $L$x [lindex $L$i]] $j$j]};incr x};incr i} [llength $L]  Try it online! Without even thinking on a "standard" method, I implement it by using Insertion Sort. Attache, 36 bytes {If[#_,Min[_]'$[Remove[_,Min!_]],_]}


Try it online!

Selection sort. Recursively sorts the list by concatenating the minimum with the sorted removed list.

import Data.Set
s=elems.fromList


Try it online!

Javascript

for(i=0;i<size;i++){for(j=i+1;j<size;j++){if(num[i]>num[j]){swap=num[j];num[j]=num[i];num[i]=swap;}}}for(i=0;i<size;i++)console.log(num[i])

Here's an implementation of bubble sort.

JavaScript, 42 bytes

a=>Object.keys(a.reduce((o,k)=>o[k]=o,{}))


Note: doesn't work for negative numbers. The iteration order of an object's keys are defined as such in the current spec, requiring that all numerical indexes are iterated in sorted numerical order first.

Pyth, 8 bytes

_ueg#G.p


Try it online!

• ueg#G.p:
• u Repeatedly apply the following function to the input until the result stops changing.
• .p: Generate all permutations of the current list
• g#G:
• #: Filter the list of permutations
• g: On being greater than or equal to
• G: The current list
• e: Take the last permutation in the filtered list. This will only be the same as the current list if the filter only leaves behind one list, because the permutation function .p always puts its input first.

At this point, we have the maximum permutation of the input, which is in reverse sorted order. _ reverses that to give the sorted list.

Note that Pyth does not have an opposite of g - there is no less than or equal to builtin.

I wanted to see what the intermediate lists are when sorting with this method. Putting a newline at the end of the code prints all of the intermediate lists:

Try it online!

For the input [0,7,4,1,6,5,2,3], here's what the intermediate lists look like:

[0, 7, 4, 1, 6, 5, 2, 3]
[3, 2, 5, 6, 1, 4, 7, 0]
[7, 0, 4, 1, 6, 5, 2, 3]
[7, 3, 2, 5, 6, 1, 4, 0]
[7, 4, 0, 1, 6, 5, 2, 3]
[7, 5, 3, 2, 6, 1, 0, 4]
[7, 6, 4, 0, 1, 2, 3, 5]
[7, 6, 5, 3, 2, 1, 0, 4]
[7, 6, 5, 4, 0, 1, 2, 3]
[7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7]


Basically, what's happening is that at each step, the (reverse) sorted prefix stays, and then the last number larger than the front unsorted number is moved to the front of the unsorted region, and the rest of the unsorted region is reversed. It's like a low-quality selection sort with reversals thrown in for fun.

I think this runs in approximately O(n^2 n!) time - n! permutations, n comparisons each, and O(n) rounds (at most 2n, from what I can tell.