Sort an Integer List

Question

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

Answer 1

05AB1E, 2 bytes

Code:

ϧ

Same algorithm as the Jelly answer. Computes all permutations of the input and pops out the smallest one.

Try it online!

---

A more efficient method is:

E[ß,Ž

Performs selection sort. Uses CP-1252 encoding.

Try it online!

Answer 2

Jelly, 3 bytes

Œ!Ṃ

This generates all permutations of the input list, then selects the lexographically smallest permutation. Very efficient.

Credits to @Adnan who had the same idea independently.

Try it online!

---

Jelly, 4 bytes

ṂrṀf

This builds the range from the minimum of the list to the maximum of the list, then discards the range elements not present in the original list. This is technically a bucket sort, with very small buckets. I'm not aware of a name for this specific variant.

Try it online!

How it works

ṂrṀf  Main link. Argument: A (list/comma-separated string)

Ṃ     Compute the minimum of A.
  Ṁ   Compute the maximum of A.
 r    Yield the inclusive range from the minimum to the maximum.
   f  Filter the range by presence in A.

Answer 3

Python, 46 45 bytes

lambda l:[l.pop(l.index(min(l)))for _ in 1*l]

Simple selection sort.

Answer 4

Brachylog, 12 7 bytes

p.'(s>)

This uses permutation sort, which is obviously terrible, but hey it's shorter than Pyth!

Explanation

p.       Unifies the output with a permutation of the input
  '(  )  True if what's inside the parentheses cannot be proven, else backtrack and
         try with another permutation of the input.
    s    Take an ordered subset from the output
     >   True if the first element is bigger than the second (hence not sorted)
         We don't need to check that the subset is 2 elements long because > will be false
         for inputs that are not 2 elements long anyway

Answer 5

Haskell, 38 bytes

h%t|(a,b)<-span(<h)t=a++h:b
foldr(%)[]

The binary function % insert a new element h into a sorted list t by partitioning t into a prefix a of elements <h and a suffix b of elements >h, and sticks in h between them.

The operation foldr(%)[] then builds up a sorted list from empty by repeatedly inserting elements from the input list.

This is one byte shorter than the direct recursive implementation

f(h:t)|(a,b)<-span(<h)$f t=a++h:b
f x=x

Another strategy for 41 bytes:

f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)

Answer 6

x86-16 machine code (BubbleSort int8_t), 20 19 bytes

x86-64/32 machine code (JumpDownSort) 21 19 bytes

Changelog:

• Thanks to @ped7g for the lodsb/cmp [si],al idea, and putting that together with a pointer increment / reset that I'd been looking at. Not needing al/ah lets us use nearly the same code for larger integers.

• New (but related) algorithm, many implementation changes: Bubbly SelectionSort allows a smaller x86-64 implementation for bytes or dwords; break-even on x86-16 (bytes or words). Also avoids the bug on size=1 that my BubbleSort has. See below.

• It turns out that my Bubbly Selection Sort with swaps every time you find a new min is already a known algorithm, JumpDown Sort. It's mentioned in Bubble Sort: An Archaeological Algorithmic Analysis (i.e. how did Bubble Sort become popular despite sucking).

---

Sorts 8-bit signed integers in-place. (Unsigned is the same code size, just change the jge to a jae). Duplicates are not a problem. We swap using a 16-bit rotate by 8 (with a memory destination).

Bubble Sort sucks for performance, but I've read that it's one of the smallest to implement in machine code. This seems especially true when there are special tricks for swapping adjacent elements. This is pretty much its only advantage, but sometimes (in real life embedded systems) that's enough advantage to use it for very short lists.

I omitted the early termination on no swaps. I used Wikipedia's "optimized" BubbleSort loop which avoids looking at the last n − 1 items when running for the n-th time, so the outer loop counter is the upper bound for the inner loop.

NASM listing (nasm -l /dev/stdout), or plain source

 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6                       
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

push/pop of cx around the inner loop means it runs with cx = outer_cx down to 0.

Note that rol r/m16, imm8 is not an 8086 instruction, it was added later (186 or 286), but this isn't trying to be 8086 code, just 16-bit x86. If SSE4.1 phminposuw would help, I'd use it.

A 32-bit version of this (still operating on 8-bit integers but with 32-bit pointers / counters) is 20 bytes (operand-size prefix on rol word [esi-1], 8)

Bug: size=1 is treated as size=65536, because nothing stops us from entering the outer do/while with cx=0. (You'd normally use jcxz for that.) But fortunately the 19-byte JumpDown Sort is 19 bytes and doesn't have that problem.

---

Original x86-16 20 byte version (without Ped7g's idea). Omitted to save space, see the edit history for it with a description.

---

Performance

Partially-overlapping store/reload (in memory-destination rotate) causes a store-forwarding stall on modern x86 CPUs (except in-order Atom). When a high value is bubbling upwards, this extra latency is part of a loop-carried dependency chain. Store/reload sucks in the first place (like 5 cycle store-forwarding latency on Haswell), but a forwarding stall brings it up to more like 13 cycles. Out-of-order execution will have trouble hiding this.

See also: Stack Overflow: bubble sort for sorting string for a version of this with a similar implementation, but with an early-out when no swaps are needed. It uses xchg al, ah / mov [si], ax for swapping, which is 1 byte longer and causes a partial-register stall on some CPUs. (But it may still be better than memory-dst rotate, which needs to load the value again). My comment there has some suggestions...

---

x86-64 / x86-32 JumpDown Sort, 19 bytes (sorts int32_t)

Callable from C using the x86-64 System V calling convention as
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (return value = max(array[])).

This is https://en.wikipedia.org/wiki/Selection_sort, but instead of remembering the position of the min element, swap the current candidate into the array. Once you've found the min(unsorted_region), store it to the end of the sorted region, like normal Selection Sort. This grows the sorted region by one. (In the code, rsi points to one past the end of the sorted region; lodsd advances it and mov [rsi-4], eax stores the min back into it.)

The name Jump Down Sort is used in Bubble Sort: An Archaeological Algorithmic Analysis. I guess my sort is really a Jump Up sort, because high elements jump upwards, leaving the bottom sorted, not the end.

This exchange design leads to the unsorted part of the array ending up in mostly reverse-sorted order, leading to lots of swaps later on. (Because you start with a large candidate, and keep seeing lower and lower candidates, so you keep swapping.) I called it "bubbly" even though it moves elements the other direction. The way it moves elements is also a little bit like a backwards insertion-sort. To watch it in action, use GDB's display (int[12])buf, set a breakpoint on the inner loop instruction, and use c (continue). Press return to repeat. (The "display" command gets GDB to print the whole array state every time we hit the breakpoint).

xchg with mem has an implicit lock prefix which makes this extra slow. Probably about an order of magnitude slower than an efficient load/store swap; xchg m,r is one per 23c throughput on Skylake, but load / store / mov with a tmp reg for an efficient swap(reg, mem) can shift one element per clock. It might be a worse ratio on an AMD CPU where the loop instruction is fast and wouldn't bottleneck the inner loop as much, but branch misses will still be a big bottleneck because swaps are common (and become more common as the unsorted region gets smaller).

 2 Address               ;; hybrib Bubble Selection sort
 3        machine         bubblyselectionsort_int32:   ;; working, 19 bytes.  Same size for int32 or int8
 4        code               ;; input: pointer in rsi, count in rcx
 5        bytes              ;; returns: eax = max
 6                       
 7                           ;dec  ecx           ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
 8                                               ; This lets us (re)enter the inner loop even for 1 element remaining.
 9                       .outer:
10                           ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56               push   rsi
12 00000001 5F               pop    rdi
13                           ;mov    edi, esi     ; rdi = min-search pointer
14 00000002 AD               lodsd
16 00000003 51               push   rcx          ; rcx = inner counter
17                       .inner:                   ; do {
18                           ; rdi points at next element to check
19                           ; eax = candidate min
20 00000004 AF               scasd                 ; cmp eax, [rdi++]
21 00000005 7E03             jle  .notmin
22 00000007 8747FC           xchg   [rdi-4], eax   ; exchange with new min.
23                         .notmin:
24 0000000A E2F8             loop  .inner          ; } while(--inner);
26                           ; swap min-position with sorted position
27                           ; eax = min.  If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC           mov    [rsi-4], eax
29 0000000F 59               pop   rcx           ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE             loop  .outer        ; } while(--unsorted);
32 00000012 C3               ret

34 00000013 13           .size: db $ - bubblyselectionsort_int32
           0x13 = 19 bytes long

Same code size for int8_t: use lodsb / scasb, AL, and change the [rsi/rdi-4] to -1. The same machine-code works in 32-bit mode for 8/32-bit elements. 16-bit mode for 8/16-bit elements needs to be re-built with the offsets changed (and 16-bit addressing modes use a different encoding). But still 19 bytes for all.

It avoids the initial dec ecx by comparing with the element it just loaded before moving on. On the last iteration of the outer loop, it loads the last element, checks if it's less than itself, then is done. This allows it to work with size=1, where my BubbleSort fails (treats it as size = 65536).

I tested this version (in GDB) using the this caller: Try it online!. You can run this it on TIO, but of course no debugger or printing. Still, the _start that calls it exits with exit-status = largest element = 99, so you can see it works.

Answer 7

JavaScript (ES6), 51 bytes

a=>a.map(_=>m=Math.min(...a.filter(e=>e>m)),m=-1/0)

Each loop finds the smallest number that hasn't been found so far.

Answer 8

Haskell, 42 41 38 bytes

f u=filter(`elem`u)[(minBound::Int)..]

Loops through all integers (signed 64bit, on my machine) and keeps those that are in u. Of course it doesn't finish in reasonable time.

The previous version looped through [minimum u..maximum u] which has the same worst case running time.

Edit: @xnor saved a byte. Thanks!

Answer 9

Oracle SQL 11.2, 205 bytes

WITH s AS(SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))),v(p,f)AS(SELECT e,e FROM s UNION ALL SELECT p||','||e,e FROM v,s WHERE e+0>f)SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1);         

Un-golfed

WITH 
s AS  -- Split the string using ',' as separator
(     -- ||'' cast the xml type to varchar
  SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))
),  
v(p,f) AS  -- Recursive view : p = sorted string, f last number added
(
  SELECT e,e FROM s -- use each number as seed
  UNION ALL         -- only add a number if it is > the last added
  SELECT p||','||e,e FROM v,s WHERE e+0>f  -- +0 is needed to compare int and not strings
)  
-- The valid string has the same length as the input
SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1)          

As for what sort method it is, I have no idea, ORDER BY made sure I forgot them.

Answer 10

Python 2, 34 bytes

def f(s):m=min(s);print m;f(s-{m})

Takes input as a set, printing its elements in increasing order, terminating with error.

A clean termination can be done in 41 bytes:

def f(s):
 if s:m=min(s);print m;f(s-{m})

or

l=input()
while l:m=min(l);print m;l-={m}

The input can be take as a list for 39 bytes, or 38 bytes in Python 3.5:

def f(l):m=min(l);print m;f(set(l)-{m})
def f(l):m=min(l);print(m);f({*l}-{m})

Answer 11

C, 72 bytes

i,j;a(int*l,int n){for(i=0;i=i?:--n;j>l[n]?l[i]=l[n],l[n]=j:0)j=l[--i];}

Bubblesort. The first argument is a pointer to the array, the second argument is the length of the array. Works with gcc.

Answer 12

MATL, 11 10 bytes

Y@t!d0>AY)

Extremely inefficient examination of all permutations of the input.

Try it Online!

Explanation

        % Implicitly grab input array
Y@      % Compute all permutations (each permutation as a row)
t       % Duplicate this matrix
!d      % Transpose and take the differences between the values
0>A     % Find the rows where all differences are > 0
Y)      % Return only the row where this is true
        % Implicitly display the result

Answer 13

Ruby, 40 bytes

Selection sort. Anonymous function; takes the list as argument.

->a{r=[];r<<a.delete(a.min)while[]!=a;r}

Answer 14

Python 3, 91 62 47 bytes

def f(z):
 while z:m=min(z);z.remove(m);yield m

Thanks to wnnmaw and Seeq for golfing help.

The argument z should be a list. This is a variant of selection sort.

I'm not sure how min stacks up against built-in sorting functions, since I'm not sure how Python implements min. Hopefully, this solution is still okay. Any golfing suggestions in the comments or in PPCG chat are welcome.

Answer 15

MATL, 11 bytes

`t4#X<2#)tn

Try it online!

This sorts by the following procedure, which is O(n²):

1. Take the minimum of the array.
2. Remove that value from the array, and store it for subsequent display.
3. Apply the same procedure with the rest of the array, until it becomes empty.
4. Display all numbers in the order in which they were obtained.

MATL is stack-based. The array with remaining values is kept at the top of the stack. The removed values are below, in order. At the end of the program all those values are displayed. The array at the top would also be displayed, but since it's empty it's not shown.

`        % Do...while loop
  t      %   Duplicate. Implicitly take input in the first iteration
  4#X<   %   Compute index of mininum of the array
  2#)    %   Push the minimum, and then the array with remaining entries
  tn     %   Duplicate and push number of elements, to be used as loop condition
         % Implicitly end do...while loop
         % Implicitly display stack contents

Answer 16

Python, 120 Bytes

def f(a):import time,threading;[threading.Thread(None,lambda b=b,c=min(a):print(time.sleep(b-c)or b)).start()for b in a]

This probably won't be the shortest answer but I feel like this algorithm belongs here. call with a list of integers, they'll be printed in a sorted manner to stdout. I wouldn't try it with too large numbers though.

Answer 17

MIPS, 68 bytes

I wrote a simple unoptimized bubble sort implementation a while ago. Byte count begins at loop and ends at li $v0, 10, assuming that the list address and list length are already in memory.

 Address    Code        Basic                     Source

0x00400000  0x3c011001  lui $1,4097           5    main:   la      $s0, list       # List address
0x00400004  0x34300000  ori $16,$1,0               
0x00400008  0x2411000a  addiu $17,$0,10       6            li      $s1, 10         # List length
0x0040000c  0x24080000  addiu $8,$0,0         8    loop:   li      $t0, 0          # swapped
0x00400010  0x24090001  addiu $9,$0,1         9            li      $t1, 1          # for loop "i"
0x00400014  0x1131000b  beq $9,$17,11         11   for:    beq     $t1, $s1, fend  # break if i==length
0x00400018  0x00095080  sll $10,$9,2          13           sll     $t2, $t1, 2     # Temp index, multiply by 4
0x0040001c  0x01505020  add $10,$10,$16       14           add     $t2, $t2, $s0   # Combined address
0x00400020  0x8d4b0000  lw $11,0($10)         15           lw      $t3, 0($t2)     # list[i]
0x00400024  0x8d4cfffc  lw $12,-4($10)        16           lw      $t4, -4($t2)    # list[i-1]
0x00400028  0x21290001  addi $9,$9,1          18           addi    $t1, $t1, 1     # i++
0x0040002c  0x016c082a  slt $1,$11,$12        20           ble     $t4, $t3, for   # if list[i-1] > list[i]
0x00400030  0x1020fff8  beq $1,$0,-8               
0x00400034  0xad4bfffc  sw $11,-4($10)        21           sw      $t3, -4($t2)    # swap and store
0x00400038  0xad4c0000  sw $12,0($10)         22           sw      $t4, 0($t2)     
0x0040003c  0x24080001  addiu $8,$0,1         23           li      $t0, 1          # swapped=true
0x00400040  0x08100005  j 0x00400014          24           j       for
0x00400044  0x20010001  addi $1,$0,1          26   fend:   subi    $s1, $s1, 1     # length--
0x00400048  0x02218822  sub $17,$17,$1             
0x0040004c  0x1500ffef  bne $8,$0,-17         27           bnez    $t0, loop       # Repeat if swapped==true
0x00400050  0x2402000a  addiu $2,$0,10        29           li      $v0, 10        
0x00400054  0x0000000c  syscall               30           syscall

Now I wait to be blown out of the water with x86...

Answer 18

Awk, 66 bytes

{b=$0;a[b]}m<b{m=b}n>b{n=b}END{for(i=n;i<=m;i++)if(i in a)print i}

Arrays in awk are like dictionaries, not like C arrays. The indexes can be non-contiguous, and they grow (and are created) as needed. So, we create an array a for the input, with each line being a key. And we save the min and max values. Then we loop from min to max, and print all keys which exist in a. b is just to avoid repeated usage of $0.

Answer 19

Pyth - 15 13 11 10 bytes

Two bytes saved thanks to @Jakube.

Bogosort.

f!s>VTtT.p

Try it online here.

I don't need the h cuz we are guaranteed no duplicates.

Answer 20

Seriously, 6 bytes

,;l@╨m

Try it online!

This does the same thing as many other answers: generate all permutations, select minimum. I kinda forgot that this would work while I was working on the below solution.

Explanation:

,;l@╨m
,;l@    push len(input), input
    ╨m  minimum permutation

---

Seriously, 25 bytes (non-competing)

This would be competitive if it wasn't for a bug in the shuffle command that I just fixed.

,1WX╚;;pX@dXZ`i@-0<`MπYWX

Try it online! This implements the best sorting algorithm ever: Bogosort!

Explanation:

,1WX╚;;pX@dXZ`i@-0<`MπYWX
,                          get input
 1W                    WX  do-while:
   X                         discard
    ╚                        shuffle
     ;;                      dupe twice
       pX@dX                 remove first element of first dupe and last element of second dupe
            Z                zip
             `i@-0<`MπY      test if all differences are positive (if any are not, the list is not sorted), negate (1 if not sorted else 0)

Answer 21

Java 8, 112 92 bytes

Here is another selection sort. The input is a List t of integers and the sorted output is printed to standard out.

t->{for(;0<t.size();System.out.println(t.remove(t.indexOf(java.util.Collections.min(t)))));}

Update

• -20 [16-08-21] Used a lambda

Answer 22

MATL, 17 16 bytes

Saved one byte creating null array thanks to @LuisMendo

vTbtX<-QI$(f8M+q

Bucket sort. Don't try it with a range greater than 2³¹-1.

Try it online!

Explanation

v                  % push an empty array
 T                 % push 1
  b                % bubble the input array up to the top of the stack
   t               % duplicate it
    X<             % find the minimum
      -            % subtract min from input array
       Q           % and increment to adjust for 1-based indexing
        I$(        % resulting array used as indices of empty array 
                   % (the [] way up at the top) that are assigned 1 (from T)
           f       % find the nonzero indices
            8M     % magically retrieve the 4th previous function input :/
                     (aka, the min input array value)
              +    % add it to the indices
               q   % and decrement

---

TIL:

• You can initialize an empty array in MATL using [] and grow it, just like in MATLAB
• How to use ( for assignment indexing
• How to use the M automatic clipboard

---

New day, new TIL:

• vertcat magically creates an empty array when there's nothing on the stack to concatenate

Answer 23

Julia, 28 27 bytes

x->colon(extrema(x)...)∩x

Try it online!

Answer 24

R, 68 Bytes

Takes input i and outputs o which is the sorted list.

o<-i
for(j in 1:length(i)){
x<-(i-min(i))==0
o[j]<-i[x]
i<-i[!x]
}
o

Explanation:

o<-i                      # Defines output as o
 for(j in 1:length(i)){   # Initializes loop for length of input
  x<-(i-min(i))==0        # Generates logical vector by finding the value 0 
                          # of input less the minimum of input. 
   o[j]<-i[x]             # Puts the smallest value at position j
    i<-i[!x]              # Removes the smallest value from input
      }                   # Ends loop
       o                  # Returns sorted list

Avoiding the permutations means it can sort large lists relatively quickly. The "trick" is that subtracting the smallest value from the input leaves a single 0 that determine both the smallest value and the position of the smallest value.

Answer 25

Clojure, 73 35 bytes

Bogosort :)

#(if(apply < %)%(recur(shuffle %)))

Earlier version:

#(reduce(fn[r i](let[[a b](split-with(partial > i)r)](concat a[i]b)))[]%)

Reduces to a sorted list r by splitting it into "smaller than i" and "larger than i" parts. I guess this is the insertion sort.

Answer 26

Ruby, 26 24 bytes

Selection sort, similar to Value Ink's answer, but using a different approach for greater golfiness.

According to the specification: "Input/output can be done in any method you choose, as long as it is human readable". I think this fits the description, output is an array of arrays with a single element.

->l{l.map{l-l-=[l.min]}}

example:

->l{l.map{l-l-=[l.min]}}[[2,4,3,1]]
=> [[1], [2], [3], [4]]

Answer 27

Java 7, 106 104 bytes

void a(int[]a){for(int b=a.length-1,d=0,c=0,e;d<b*b;c=++d%b)if(a[c]>a[c+1]){e=a[c];a[c++]=a[c];a[c]=e;}}

Here's a good ole bubble sort. The function parameter is modified in place so I don't have to return anything. Still trying to squeeze some bytes out of this so I can beat the java lambda that someone posted.

-1 byte thanks to Geobits for pointing out that normal swapping beats xor'ing
-1 byte thanks to Leaky Nun for pointing out that I can move all the int declarations into the for-loop

Try it online!

Answer 28

Ruby, 22 bytes

->a{[*a.min..a.max]&a}

Builds an array out of the range between the minimum and maximum elements of the input array. Returns the intersection between the two arrays.

Answer 29

Python 3, 53 bytes

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

Try it online!

Answer 30

Retina, 95

Modified bubble sort. I suspect there are much better ways to do this, even without the retina sort builtin.

-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&

• Stage 1 - convert -ve integers to unary with n as the digit; drop the - signs.
• Stage 2 - convert +ve and zero integers to unary with 1 as the digit; add 1 to each one, so that zero is represented by 1.
• Stage 3 - Move all -ves to the front.
• Stage 4 - Sort: move all -ves with the largest magnitude (i.e. smallest numerical) ahead of higher -ves. Move smaller +ves ahead of larger +ves.
• Stage 5 - Remove 1 from, and convert +ve unaries back to decimal.
• Stage 6 - convert -ve unaries back to decimal, including sign.

Try it online.

Answer 31

Ruby, 22 bytes

A quick permutation sort. Runs in O(n!) space and time.

->a{a.permutation.min}

Answer 32

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

Answer 33

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.

Answer 34

Perl 5, 65 bytes

Insertion sort subroutine:

sub r{map{$t=0;$_[$_]<$_[$t]&&($t=$_)for 0..$#_;splice@_,$t,1}@_}

Try it online!

Answer 35

R, 47 bytes

implements bogosort.

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

Try it online!

Answer 36

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.

Answer 37

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

Answer 38

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

Answer 39

Javascript 55 bytes

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

Answer 40

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.

Answer 41

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.

Answer 42

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.

Answer 43

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.

Answer 44

Haskell, 3332 bytes

import Data.Set
s=elems.fromList

Try it online!

Answer 45

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.

Answer 46

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.

Answer 47

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.