View source for Compare sorting algorithms' performance

{{task|Sorting Algorithms}}
[[Category:Sorting]]
{{Sorting Algorithm}}

Measure a relative performance of sorting algorithms implementations.

Plot '''execution time vs. input sequence length''' dependencies for various implementation of sorting algorithm and different input sequence types ([[#Figures: log2( time in microseconds ) vs. log2( sequence length )|example figures]]). 

Consider three type of input sequences:
:* &nbsp; ones: sequence of all ''1'''s. &nbsp; Example: {1, 1, 1, 1, 1}
:* &nbsp; range: ascending sequence, i.e. already sorted. &nbsp; Example: {1, 2, 3, 10, 15}
:* &nbsp; shuffled range: sequence with elements randomly distributed. &nbsp; Example: {5, 3, 9, 6, 8}


Consider at least two different sorting functions (different algorithms or/and different implementation of the same algorithm).

For example, consider [[Bubble Sort]], [[Insertion sort]], [[Quicksort]] or/and implementations of Quicksort with different pivot selection mechanisms. &nbsp; Where possible, use existing implementations.

Preliminary subtask:
:* &nbsp; [[Bubble Sort]], [[Insertion sort]], [[Quicksort]], [[Radix sort]], [[Shell sort]]
:* &nbsp; [[Query Performance]]
:* &nbsp; [[Write float arrays to a text file]]
:* &nbsp; [[Plot x, y arrays]]
:* &nbsp; [[Polynomial Fitting]]


General steps:
:# &nbsp; Define sorting routines to be considered.
:# &nbsp; Define appropriate sequence generators and write timings.
:# &nbsp; Plot timings.
:# &nbsp; What conclusions about relative performance of the sorting routines could be made based on the plots?
<br><br>

=={{header|AutoHotkey}}==
{{in progress|lang=AutoHotkey|day=16|month=1|year=2010}}
<syntaxhighlight lang="ahk">; BUGGY - FIX

#Persistent
#SingleInstance OFF
SetBatchLines, -1
SortMethods := "Bogo,Bubble,Cocktail,Counting,Gnome,Insertion,Merge,Permutation,Quick,Selection,Shell,BuiltIn"
Gui, Add, Edit, vInput, numbers,separated,by,commas,without,spaces,afterwards
Loop, PARSE, SortMethods, `,
	Gui, Add, CheckBox, v%A_LoopField%, %A_LoopField% Sort
Gui, Add, Button, gTest, Test!
Gui, Show,, SortTest!
Return
Test:
SplashTextOn,,, Test Commencing
Sleep 2500
SplashTextOff
Gui, +OwnDialogs
Gui, Submit, NoHide
Loop, PARSE, SortMethods, `,
{
	If (%A_LoopField%)
	{
		DllCall("QueryPerformanceCounter", "Int64 *", %A_LoopField%Begin)
		%A_LoopField%Out := %A_LoopField%Sort(Input)
		DllCall("QueryPerformanceCounter", "Int64 *", %A_LoopField%Time)
		%A_LoopField%End := %A_LoopField%Begin + %A_LoopField%Time
		%A_LoopField%Time -= %A_LoopField%Begin
	}
}
Time := ""
Loop, PARSE, SortMethods, `,
	If (%A_LoopField%)
		Time .= A_LoopField . " Sort: " . %A_LoopField%Time . "`t`t" . %A_LoopField%Out . "`r`n"
MsgBox,, Results!, %Time%
Return



; Sorting funtions (Bogo, Bubble, Cocktail, Counting, Gnome, Insertion, Merge, Permutation, Quick, Selection, Shell, BuiltIn):

BogoSort(var)
{
	sorted := 1
	Loop, Parse, var
	{
		current := A_LoopField
		rest := SubStr(var, A_Index)
		Loop, Parse, rest
		{
			If (current > A_LoopField)
			sorted := 0
		}
	}
	While !sorted {
		sorted := 1
		Loop, Parse, var, `,
		{
			current := A_LoopField
			rest := SubStr(var, A_Index)
			Loop, Parse, rest, `,
			{
				If (current > A_LoopField)
				sorted := 0
			}
		}

		Sort, var, D`, Random
	}
	Return var
}

BubbleSort(var)
{ 
	StringSplit, array, var, `,
	hasChanged = 1
	size := array0
	While hasChanged
	{
		hasChanged = 0
		Loop, % (size - 1)
		{
			i := array%A_Index%
			aj := A_Index + 1
			j := array%aj%
			If (j < i)
			{
				temp := array%A_Index%
				array%A_Index% := array%aj%
				array%aj% := temp
				hasChanged = 1
			} 
		}
	}
	Loop, % size
	sorted .= "," . array%A_Index%
	Return substr(sorted,2)
}

CocktailSort(var)
{
	StringSplit array, var, `,
	i0 := 1, i1 := array0
	Loop
	{
		Changed =
		Loop % i1-- -i0 {
			j := i0+A_Index, i := j-1
			If (array%j% < array%i%)
				t := array%i%, array%i% := array%j%, array%j% := t
				,Changed = 1
		}
		IfEqual Changed,, Break
		Loop % i1-i0++
		{
			i := i1-A_Index, j := i+1
			If (array%j% < array%i%)
			t := array%i%, array%i% := array%j%, array%j% := t
			,Changed = 1
		}
		IfEqual Changed,, Break
	}
	Loop % array0
		sorted .= "," . array%A_Index%
	Return SubStr(sorted,2)
}

CountingSort(var)
{
	max := min := substr(var, 1, instr(var, ","))
	Loop, parse, var, `,
	{
		If (A_LoopField > max)
			max := A_LoopField

		Else If (A_LoopField < min)
			min := A_LoopField
	}
	Loop % max-min+1
		i := A_Index-1, a%i% := 0
	Loop, Parse, var, `,
		i := A_LoopField-min, a%i%++
	Loop % max-min+1
	{
		i := A_Index-1, v := i+min
		Loop % a%i%
			t .= "," v
	}
	Return SubStr(t,2)
}

GnomeSort(var) {
	StringSplit, a, var, `,
	i := 2, j := 3
	While i <= a0 {
		u := i-1
		If (a%u% < a%i%)
			i := j, j := j+1
		Else {
			t := a%u%, a%u% := a%i%, a%i% := t
			If (--i = 1)
				i := j, j++
		}
	}
	Loop % a0
	sorted .= "," . a%A_Index%
	Return SubStr(sorted,2)
}

InsertionSort(var) {
	StringSplit, a, var, `,
	Loop % a0-1 {
		i := A_Index+1, v := a%i%, j := i-1
		While j>0 and a%j%>v
			u := j+1, a%u% := a%j%, j--
		u := j+1, a%u% := v
	}
	Loop % a0
	sorted .= "," . a%A_Index%
	Return SubStr(sorted,2)
}


MergeSort(var) {
	StringReplace, t, var, `,,, UseErrorLevel
	L := ((t = "") ? 0 : ErrorLevel+1)
	If (2 > L)
		Return var
	StringGetPos, p, var, `,, % "L" L//2
	list0 := MergeSort(SubStr(var,1,p))
	list1 := MergeSort(SubStr(var,p+2))
	If (list0 = "")
		Return list1
	Else If (list1 = "")
		Return list0
	list := list0
	i0 := (p0 := InStr(list,",",0,i:=p0+1)) ? SubStr(list,i,p0-i) : SubStr(list,i)
	list := list1
	i1 := (p1 := InStr(list,",",0,i:=p1+1)) ? SubStr(list,i,p1-i) : SubStr(list,i)
	Loop  {
		i := i0>i1
		list .= "," i%i%
		If (p%i%) {
			list := list%i%
			i%i% := (p%i% := InStr(list,",",0,i:=p%i%+1)) ? SubStr(list,i,p%i%-i) : SubStr(list,i)
		}
		Else {
			i ^= 1
			rtv := SubStr(list "," i%i% (p%i% ? "," SubStr(list%i%,p%i%+1) : ""), 2)
		}
	}
	Return rtv
}

PermutationSort(var) {
	static a:="a",v:="v"
	StringSplit, a, var, `,
	v0 := a0
	Loop %v0%
		v%A_Index% := A_Index
	unsorted := 0
	Loop % %a%0-1 {
		i := %v%%A_Index%, j := A_Index+1, j := %v%%j%
		If (%a%%i% > %a%%j%)
			unSorted := 1
	}
	While unSorted {
		i := %v%0, i1 := i-1
		While %v%%i1% >= %v%%i% {
			--i, --i1
			IfLess i1,1, Return 1
		}
		j := %v%0
		While %v%%j% <= %v%%i1%
			--j
		t := %v%%i1%, %v%%i1% := %v%%j%, %v%%j% := t,  j := %v%0
		While i < j
			t := %v%%i%, %v%%i% := %v%%j%, %v%%j% := t, ++i, --j
		unsorted := 0
		Loop % %a%0-1 {
			i := %v%%A_Index%, j := A_Index+1, j := %v%%j%
			If (%a%%i% > %a%%j%)
				unSorted := 1
		}
	}
	Loop % a0
		i := v%A_Index%, sorted .= "," . a%i%
	Return SubStr(sorted,2)
}

QuickSort(var)
{
	StringSplit, list, var, `,
	If (list0 <= 1)
		Return list
	pivot := list1
	Loop, Parse, var, `,
	{
		If (A_LoopField < pivot)
			less .= "," . A_LoopField
		Else If (A_LoopField > pivot)
			more .= "," . A_LoopField
		Else
			pivotlist .= "," . A_LoopField
	}
	less := QuickSort(substr(less,2))
	more := QuickSort(substr(more,2))
	Return substr(less,2) . pivotList . more
}

SelectionSort(var) {
	StringSplit, a, var, `,
	Loop % a0-1 {
		i := A_Index, mn := a%i%, j := m := i
		Loop % a0-i {
			j++
			If (a%j% < mn)
				mn := a%j%, m := j
		}
		t := a%i%, a%i% := a%m%, a%m% := t
	}
	Loop % a0
		sorted .= "," . a%A_Index%
	Return SubStr(sorted,2)
}

ShellSort(var) {
	StringSplit, a, var, `,
	inc := a0
	While inc:=round(inc/2.2)
		Loop % a0-inc {
			i := A_Index+inc, t := a%i%, j := i, k := j-inc
			While j > inc && a%k% > t
				a%j% := a%k%, j := k, k -= inc
			a%j% := t
		}
	Loop % a0
		s .= "," . a%A_Index%
	Return SubStr(s,2)
}

BuiltInSort(var) {
	Sort, var, N D`,
	Return var
}</syntaxhighlight>


=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">#Macro sort_1(sortname)
    Rset buffer, #sortname
    Print buffer;
    copy_array(rev(), sort())
    t1 = Timer
    sortname(sort())
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    copy_array(ran(), sort())
    t1 = Timer
    sortname(sort())
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    t1 = Timer
    sortname(sort())
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    copy_array(eq(), sort())
    t1 = Timer
    sortname(sort())
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec"
#EndMacro

#Macro sort_2(sortname)
    Rset buffer, #sortname
    Print buffer;
    copy_array(rev(), sort())
    t1 = Timer
    sortname(sort(), Lbound(sort), Ubound(sort))
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    copy_array(ran(), sort())
    t1 = Timer
    sortname(sort(), Lbound(sort), Ubound(sort))
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    t1 = Timer
    sortname(sort(), Lbound(sort), Ubound(sort))
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec";
    copy_array(eq(),sort())
    t1 = Timer
    sortname(sort(), Lbound(sort), Ubound(sort))
    t2 = Timer - t1
    Print Using "  ###.###&"; t2; " sec"
#EndMacro


Sub bubbleSort(array() As Double)
    Dim As Integer i, lb = Lbound(array), ub = Ubound(array)
    
    For p1 As Uinteger = 0 To ub - 1
        For p2 As Uinteger = p1 + 1 To ub
            'change >= to > , don't swap if they are equal
            If (array(p1)) > (array(p2)) Then Swap array(p1), array(p2)
        Next p2
    Next p1
    For i = lb To ub - 1
        If array(i) > array(i + 1) Then Beep
    Next
End Sub

Sub exchangeSort(array() As Double)
    Dim As Uinteger i, j, min, ub = Ubound(array)
    For i = 0 To ub
        min = i
        For j = i+1 To ub
            If (array(j) < array(min)) Then min = j
        Next j
        If min > i Then Swap array(i), array(min)
    Next i
End Sub

Sub insertionSort(array() As Double)
    Dim As Uinteger ub = Ubound(array)
    Dim As Uinteger i, j, temp, temp2
    
    For i = 1 To ub
        temp = array(i)
        temp2 = temp
        j = i
        While j >= 1 Andalso array(j-1) > temp2
            array(j) = array(j - 1)
            j -= 1
        Wend
        array(j) = temp
    Next i
End Sub

Sub siftdown(hs() As Double, inicio As Ulong, final As Ulong)
    Dim As Ulong root = inicio
    Dim As Long lb = Lbound(hs)
    
    While root * 2 + 1 <= final
        Dim As Ulong child = root * 2 + 1
        If (child + 1 <= final) Andalso (hs(lb + child) < hs(lb + child + 1)) Then child += 1
        If hs(lb + root) < hs(lb + child) Then
            Swap hs(lb + root), hs(lb + child)
            root = child
        Else
            Return
        End If
    Wend
End Sub
Sub heapSort(array() As Double)
    Dim As Long lb = Lbound(array)
    
    Dim As Ulong count = Ubound(array) - lb + 1
    Dim As Long inicio = (count - 2) \ 2
    Dim As Ulong final = count - 1
    
    While inicio >= 0
        siftdown(array(), inicio, final)
        inicio -= 1
    Wend
    
    While final > 0
        Swap array(lb + final), array(lb)
        final -= 1
        siftdown(array(), 0, final)
    Wend
End Sub

Sub shellSort(array() As Double)
    Dim As Uinteger lb = Lbound(array), ub = Ubound(array)
    Dim As Uinteger i, inc = ub - lb
    Dim As Boolean done
    
    Do
        inc = Int(inc / 2.2)
        If inc < 1 Then inc = 1
        
        Do
            done = false
            For i = lb To ub - inc
                ' reemplace "<" con ">" para ordenación descendente
                If array(i) > array(i + inc) Then
                    Swap array(i), array(i + inc)
                    done = true
                End If
            Next i
        Loop Until done = false
    Loop Until inc = 1
End Sub

Sub quickSort(array() As Double, l As Integer, r As Integer)
    Dim As Uinteger size = r - l +1
    If size < 2 Then Exit Sub
    
    Dim As Integer i = l, j = r
    Dim As Double pivot = array(l + size \ 2)
    
    Do
        While array(i) < pivot
            i += 1
        Wend
        While pivot < array(j)
            j -= 1
        Wend
        If i <= j Then
            Swap array(i), array(j)
            i += 1
            j -= 1
        End If
    Loop Until i > j
    
    If l < j Then quickSort(array(), l, j)
    If i < r Then quickSort(array(), i, r)
End Sub

Sub rapidSort (array()As Double, inicio As Integer, final As Integer)
    Dim As Integer n, wert, nptr, arr, rep
    Dim As Integer LoVal = array(inicio), HiVal = array(final)
    For n = inicio To final
        If LoVal> array(n) Then LoVal = array(n)
        If HiVal< array(n) Then HiVal = array(n)
    Next
    Redim SortArray(LoVal To HiVal) As Double
    For n = inicio To final
        wert = array(n)
        SortArray(wert) += 1
    Next
    nptr = inicio-1
    For arr = LoVal To HiVal
        rep = SortArray(arr)
        For n = 1 To rep
            nptr += 1
            array(nptr) = arr
        Next
    Next
    Erase SortArray
End Sub

Sub copy_array(s() As Double, d() As Double)
    For x As Integer = Lbound(s) To Ubound(s)
        d(x) = s(x)
    Next
End Sub


Dim As Integer x, max = 1e5
Dim As Double t1, t2, ran(0 To max), sort(0 To max), rev(0 To max), eq(0 To max)
Dim As String buffer = Space(14)

Cls
' fill ran() with random numbers and eq() with same number
For x = 0 To max
    ran(x) = Rnd
    rev(x) = ran(x)   ' make reverse array equal to random array
    eq(x) = 1/3
Next x

For x = Lbound(rev) To (Ubound(rev) \ 2)
    Swap rev(x), rev(Ubound(rev) - x)
Next x

Print !"Test times in sec\nArray size ="; max
Print !"\n                 *Reversed*   *Random*     *Sorted*     *All ones*"

sort_1(bubbleSort)
sort_1(exchangeSort)
sort_1(insertionSort)
sort_1(heapSort)
sort_1(shellSort)
sort_2(quickSort)
sort_2(rapidSort)
Sleep</syntaxhighlight>
{{out}}
<pre>Test times in sec
Array size = 100000

                 *Reversed*   *Random*     *Sorted*     *All ones*
    bubbleSort   31.645 sec   31.560 sec   12.765 sec   12.754 sec
  exchangeSort   12.706 sec   12.708 sec   12.713 sec   12.700 sec
 insertionSort    4.724 sec    4.739 sec    0.004 sec    0.004 sec
      heapSort    0.028 sec    0.029 sec    0.021 sec    0.002 sec
     shellSort    0.049 sec    0.049 sec    0.003 sec    0.003 sec
     quickSort    0.013 sec    0.013 sec    0.004 sec    0.005 sec
     rapidSort    0.004 sec    0.004 sec    0.004 sec    0.007 sec</pre>


=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic">      HIMEM = PAGE + 2000000
      INSTALL @lib$+"SORTLIB"
      INSTALL @lib$+"TIMERLIB"
      Sort% = FN_sortinit(0,0)
      Timer% = FN_ontimer(1000, PROCtimer, 1)
      
      PRINT "Array size:", 1000, 10000, 100000
      @% = &2020A
      
      FOR patt% = 1 TO 4
        CASE patt% OF
          WHEN 1: PRINT '"Data set to all ones:"
          WHEN 2: PRINT '"Data ascending sequence:"
          WHEN 3: PRINT '"Data randomly shuffled:"
          WHEN 4: PRINT '"Data descending sequence:"
        ENDCASE
        
        FOR type% = 1 TO 6
          CASE type% OF
            WHEN 1: PRINT "Internal (lib)";
            WHEN 2: PRINT "Quicksort   ";
            WHEN 3: PRINT "Radix sort  ";
            WHEN 4: PRINT "Shellsort   ";
            WHEN 5: PRINT "Bubblesort  ";
            WHEN 6: PRINT "Insertion sort";
          ENDCASE
          
          FOR power% = 3 TO 5
            PROCsorttest(patt%, type%, 10^power%)
          NEXT
          PRINT
          
        NEXT type%
      NEXT patt%
      END
      
      DEF PROCsorttest(patt%, type%, size%)
      LOCAL a%(), C%, I%
      DIM a%(size%-1)
      
      CASE patt% OF
        WHEN 1: a%() = 1 : a%() = 1
        WHEN 2: FOR I% = 0 TO size%-1 : a%(I%) = I% : NEXT
        WHEN 3: FOR I% = 0 TO size%-1 : a%(I%) = I% : NEXT
          C% = RND(-123456) : REM Seed
          FOR I% = size% TO 2 STEP -1 : SWAP a%(I%-1),a%(RND(I%)-1) : NEXT
        WHEN 4: FOR I% = 0 TO size%-1 : a%(I%) = size%-1-I% : NEXT
      ENDCASE
      
      Start% = TIME
      ON ERROR LOCAL PRINT , "   >100.00" ; : ENDPROC
      CASE type% OF
        WHEN 1: C% = size% : CALL Sort%, a%(0)
        WHEN 2: PROCquicksort(a%(), 0, size%)
        WHEN 3: PROCradixsort(a%(), size%, 10)
        WHEN 4: PROCshellsort(a%(), size%)
        WHEN 5: PROCbubblesort(a%(), size%)
        WHEN 6: PROCinsertionsort(a%(), size%)
      ENDCASE
      PRINT , (TIME - Start%)/100;
      
      FOR I% = 0 TO size%-2
        IF a%(I%) > a%(I%+1) ERROR 100, "Sort failed!"
      NEXT
      ENDPROC
      
      DEF PROCtimer
      Start% += 0
      IF (TIME - Start%) > 10000 ERROR 111, ""
      ENDPROC
      
      DEF PROCbubblesort(a%(), n%)
      LOCAL i%, l%
      REPEAT
        l% = 0
        FOR i% = 1 TO n%-1
          IF a%(i%-1) > a%(i%) THEN
            SWAP a%(i%-1),a%(i%)
            l% = i%
          ENDIF
        NEXT
        n% = l%
      UNTIL l% = 0
      ENDPROC
      
      DEF PROCinsertionsort(a%(), n%)
      LOCAL i%, j%, t%
      FOR i% = 1 TO n%-1
        t% = a%(i%)
        j% = i%
        WHILE j%>0 AND t%<a%(ABS(j%-1))
          a%(j%) = a%(j%-1)
          j% -= 1
        ENDWHILE
        a%(j%) = t%
      NEXT
      ENDPROC
      
      DEF PROCquicksort(a%(), s%, n%)
      LOCAL l%, p%, r%, t%
      IF n% < 2 THEN ENDPROC
      t% = s% + n% - 1
      l% = s%
      r% = t%
      p% = a%((l% + r%) DIV 2)
      REPEAT
        WHILE a%(l%) < p% l% += 1 : ENDWHILE
        WHILE a%(r%) > p% r% -= 1 : ENDWHILE
        IF l% <= r% THEN
          SWAP a%(l%), a%(r%)
          l% += 1
          r% -= 1
        ENDIF
      UNTIL l% > r%
      IF s% < r% PROCquicksort(a%(), s%, r% - s% + 1)
      IF l% < t% PROCquicksort(a%(), l%, t% - l% + 1 )
      ENDPROC
      
      DEF PROCshellsort(a%(), n%)
      LOCAL h%, i%, j%, k%
      h% = n%
      WHILE h%
        IF h% = 2 h% = 1 ELSE h% DIV= 2.2
        FOR i% = h% TO n% - 1
          k% = a%(i%)
          j% = i%
          WHILE j% >= h% AND k% < a%(ABS(j% - h%))
            a%(j%) = a%(j% - h%)
            j% -= h%
          ENDWHILE
          a%(j%) = k%
        NEXT
      ENDWHILE
      ENDPROC
      
      DEF PROCradixsort(a%(), n%, r%)
      LOCAL d%, e%, i%, l%, m%, b%(), bucket%()
      DIM b%(DIM(a%(),1)), bucket%(r%-1)
      FOR i% = 0 TO n%-1
        IF a%(i%) < l% l% = a%(i%)
        IF a%(i%) > m% m% = a%(i%)
      NEXT
      a%() -= l%
      m% -= l%
      e% = 1
      WHILE m% DIV e%
        bucket%() = 0
        FOR i% = 0 TO n%-1
          bucket%(a%(i%) DIV e% MOD r%) += 1
        NEXT
        FOR i% = 1 TO r%-1
          bucket%(i%) += bucket%(i% - 1)
        NEXT
        FOR i% = n%-1 TO 0 STEP -1
          d% = a%(i%) DIV e% MOD r%
          bucket%(d%) -= 1
          b%(bucket%(d%)) = a%(i%)
        NEXT
        a%() = b%()
        e% *= r%
      ENDWHILE
      a%() += l%
      ENDPROC</syntaxhighlight>
'''Output:'''
<pre>
Array size:               1000     10000    100000

Data set to all ones:
Internal (lib)            0.00      0.01      0.03
Quicksort                 0.02      0.27      3.18
Radix sort                0.01      0.05      0.53
Shellsort                 0.03      0.36      4.44
Bubblesort                0.00      0.01      0.09
Insertion sort            0.00      0.02      0.26

Data ascending sequence:
Internal (lib)            0.00      0.00      0.02
Quicksort                 0.02      0.15      1.82
Radix sort                0.02      0.18      2.10
Shellsort                 0.03      0.37      4.44
Bubblesort                0.00      0.01      0.09
Insertion sort            0.01      0.03      0.27

Data randomly shuffled:
Internal (lib)            0.00      0.02      0.44
Quicksort                 0.02      0.26      3.17
Radix sort                0.02      0.17      2.08
Shellsort                 0.04      0.73     11.57
Bubblesort                0.69     69.70   >100.00
Insertion sort            0.55     55.54   >100.00

Data descending sequence:
Internal (lib)            0.00      0.01      0.10
Quicksort                 0.01      0.15      1.90
Radix sort                0.02      0.17      2.06
Shellsort                 0.03      0.50      6.39
Bubblesort                0.95     94.77   >100.00
Insertion sort            1.11   >100.00   >100.00
</pre>

=={{header|C}}==
(The reference example is [[Measure relative performance of sorting algorithms implementations#Python|Python]])
===Examples of sorting routines===
We can use the codes in the category [[:Category:Sorting Algorithms|Sorting Algorithms]]; since these codes deal with integer arrays, we should change them a little. To accomplish this task I've also renamed them more consistently <tt>algorithm_sort</tt>; so we have e.g. <tt>bubble_sort</tt>, <tt>quick_sort</tt> and so on.
===Sequence generators===
<tt>csequence.h</tt>
<syntaxhighlight lang="c">#ifndef _CSEQUENCE_H
#define _CSEQUENCE_H
#include <stdlib.h>

void setfillconst(double c);
void fillwithconst(double *v, int n);
void fillwithrrange(double *v, int n);
void shuffledrange(double *v, int n);
#endif</syntaxhighlight>
<tt>csequence.c</tt>
<syntaxhighlight lang="c">#include "csequence.h"

static double fill_constant;

void setfillconst(double c)
{
  fill_constant = c;
}

void fillwithconst(double *v, int n)
{
  while( --n >= 0 ) v[n] = fill_constant;
}

void fillwithrrange(double *v, int n)
{
  int on = n;
  while( --on >= 0 ) v[on] = n - on;
}

void shuffledrange(double *v, int n)
{
  int on = n;
  fillwithrrange(v, n);
  while( --n >= 0 ) {
    int r = rand() % on;
    double t = v[n];
    v[n] = v[r];
    v[r] = t;
  }
}</syntaxhighlight>
===Write timings===
We shall use the code from [[Query Performance]]. Since the ''action'' is a generic function with a single argument, we need ''wrappers'' which encapsule each sorting algorithms we want to test.

<tt>writetimings.h</tt>
<syntaxhighlight lang="c">#ifndef _WRITETIMINGS_H
#define _WRITETIMINGS_H
#include "sorts.h"
#include "csequence.h"
#include "timeit.h"

/* we repeat the same MEANREPEAT times, and get the mean; this *should*
   give "better" results ... */
#define MEANREPEAT 10.0
#define BUFLEN 128
#define MAKEACTION(ALGO) \
  int action_ ## ALGO (int size) {				\
    ALGO ## _sort(tobesorted, size);				\
    return 0; }
#define MAKEPIECE(N) { #N , action_ ## N }

int action_bubble(int size);
int action_shell(int size);
int action_quick(int size);
int action_insertion(int size);
int action_merge(int size);
int doublecompare( const void *a, const void *b );
int action_qsort(int size);
int get_the_longest(int *a);

struct testpiece
{
  const char *name;
  int (*action)(int);
};
typedef struct testpiece testpiece_t;

struct seqdef
{
  const char *name;
  void (*seqcreator)(double *, int);
};
typedef struct seqdef seqdef_t;
#endif</syntaxhighlight>
<tt>writetimings.c</tt>
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>

#include "writetimings.h"

double *tobesorted = NULL;
const char *bname = "data_";
const char *filetempl = "%s%s_%s.dat";
int datlengths[] = {100, 200, 300, 500, 1000, 5000, 10000, 50000, 100000};

testpiece_t testpieces[] =
{
//  MAKEPIECE(bubble),
  MAKEPIECE(shell),
  MAKEPIECE(merge),
  MAKEPIECE(insertion),
  MAKEPIECE(quick),
  MAKEPIECE(qsort),
  { NULL, NULL }
};

seqdef_t seqdefs[] =
{
  { "c1", fillwithconst },
  { "rr", fillwithrrange },
  { "sr", shuffledrange },
  { NULL, NULL }
};


MAKEACTION(bubble)
MAKEACTION(insertion)
MAKEACTION(quick)
MAKEACTION(shell)

int action_merge(int size)
{
  double *res = merge_sort(tobesorted, size);
  free(res); /* unluckly this affects performance */
  return 0;
}

int doublecompare( const void *a, const void *b )
{
  if ( *(const double *)a < *(const double *)b ) return -1;
  else return *(const double *)a > *(const double *)b;
}
int action_qsort(int size)
{
  qsort(tobesorted, size, sizeof(double), doublecompare);
  return 0;
}

int get_the_longest(int *a)
{
  int r = *a;
  while( *a > 0 ) {
    if ( *a > r ) r = *a;
    a++;
  }
  return r;
}


int main()
{
  int i, j, k, z, lenmax;
  char buf[BUFLEN];
  FILE *out;
  double thetime;

  lenmax = get_the_longest(datlengths);
  printf("Bigger data set has %d elements\n", lenmax);
  tobesorted = malloc(sizeof(double)*lenmax);
  if ( tobesorted == NULL ) return 1;

  setfillconst(1.0);

  for(i=0; testpieces[i].name != NULL; i++) {
    for(j=0; seqdefs[j].name != NULL; j++) {
      snprintf(buf, BUFLEN, filetempl, bname, testpieces[i].name,
	       seqdefs[j].name);
      out = fopen(buf, "w");
      if ( out == NULL ) goto severe;
      printf("Producing data for sort '%s', created data type '%s'\n", 
	     testpieces[i].name, seqdefs[j].name);
      for(k=0; datlengths[k] > 0; k++) {
	printf("\tNumber of elements: %d\n", datlengths[k]);
	thetime = 0.0;
	seqdefs[j].seqcreator(tobesorted, datlengths[k]);
	fprintf(out, "%d ", datlengths[k]);
	for(z=0; z < MEANREPEAT; z++) {
	  thetime += time_it(testpieces[i].action, datlengths[k]);
	}
	thetime /= MEANREPEAT;
	fprintf(out, "%.8lf\n", thetime);
      }
      fclose(out);
    }
  }
severe:
  free(tobesorted);
  return 0;
}</syntaxhighlight>
This code produce several files with the following naming convention:
* data_''algorithm''_''sequence''.dat
Where ''algorithm'' is one of the following: insertion, merge, shell, quick, qsort (the quicksort in the libc library) (bubble sort became too slow for longest sequences). ''Sequence'' is ''c1'' (constant value 1), ''rr'' (reverse range), ''sr'' (shufled range). These data can be easily plotted by Gnuplot, which can also do fitting. Instead we do our fitting using [[Polynomial Fitting]].
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "polifitgsl.h"

#define MAXNUMOFDATA 100

double x[MAXNUMOFDATA], y[MAXNUMOFDATA];
double cf[2];

int main()
{
  int i, nod;
  int r;

  for(i=0; i < MAXNUMOFDATA; i++)
  {
    r = scanf("%lf %lf\n", &x[i], &y[i]);
    if ( (r == EOF) || (r < 2) ) break;
    x[i] = log10(x[i]);
    y[i] = log10(y[i]);
  }
  nod = i;

  polynomialfit(nod, 2, x, y, cf);
  printf("C0 = %lf\nC1 = %lf\n", cf[0], cf[1]);

  return 0;
}</syntaxhighlight>
Here we search for a fit with C<sub>0</sub>+C<sub>1</sub>x "in the log scale", since we supposed the data, once plotted on a logscale graph, can be fitted by a line. We can use e.g. a shell one-liner to produce the parameters for the line for each data file previously output. In particular I've used the following
<pre>for el in *.dat ; do fitdata <$el >${el%.dat}.fd ; done</pre>

===Plot timings and Figures===
Once we have all the ".dat" files and associated ".fd", we can use Gnuplot to draw our '''data''' and think about conclusions (we could also use the idea in [[Plot x, y arrays]], but it needs too much enhancements to be usable for this analysis). Here an example of such a draw for a single file (using Gnuplot)
<pre>
gnuplot> f(x) = C0 + C1*x
gnuplot> set logscale xy
gnuplot> load 'data_quick_sr_u.fd'
gnuplot> set xrange [100:100000]
gnuplot> set key left
gnuplot> plot 10**f(log10(x)), 'data_quick_sr_u.dat'
</pre>
(The <tt>_u.dat</tt> are produced by a modified version of the code in order to write timings in microseconds instead of seconds)
We can easily write another shell script/one-liner to produce a single file ''driver'' for Gnuplot in order to produce all the graph we can be interested in.
These graphs show that the linear (in log scale) fit do not always fit the data... I haven't repeated the tests; the problems are when the sequence length becomes huge; for some algorithm that uses extra memory (like implementation of the merge sort), this could depend on the allocation of the needed memory. Another ''extraneous'' factor could be system load (the CLOCK_MONOTONIC used by the timing function is system wide rather than per process, so counting time spent in other processes too?).
The "most stable" algorithms seem to be quick sort (but not qsort, which indeed is just the libc quick sort, here not plotted!) and shell sort (except for reversed range).

Conclusion: we should repeat the tests...
* [http://i40.tinypic.com/2dabyb7.png sequences of 1]
* [http://i43.tinypic.com/2nqrzfs.png reversed range]
* [http://i41.tinypic.com/24q8hmg.png shuffled range]


=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.container, std.datetime,
       std.random, std.typetuple;

immutable int[] allOnes, sortedData, randomData;

static this() { // Initialize global Arrays.
    immutable size_t arraySize = 10_000;

    allOnes = new int[arraySize];
    //allOnes[] = 1;
    foreach (ref d; allOnes)
        d = 1;

    sortedData = new int[arraySize];
    foreach (immutable i, ref d; sortedData)
        d = i;

    randomData = new int[arraySize];
    foreach (ref d; randomData)
        d = uniform(0, int.max);
}

// BubbleSort:

void bubbleSort(T)(T[] list) {
    for (int i = list.length - 1; i > 0; i--)
        for (int j = i -1; j >= 0; j--)
            if (list[i] < list[j])
                swap(list[i], list[j]);
}

void allOnesBubble() {
    auto data = allOnes.dup;
    data.bubbleSort;
    assert(data.isSorted);
}

void sortedBubble() {
    auto data = sortedData.dup;
    data.bubbleSort;
    assert(data.isSorted);
}

void randomBubble() {
    auto data = randomData.dup;
    data.bubbleSort;
    assert(data.isSorted);
}

// InsertionSort:

void insertionSort(T)(T[] list) {
    foreach (immutable i, currElem; list) {
        size_t j = i;
        for (; j > 0 && currElem < list[j - 1]; j--)
            list[j] = list[j - 1];
        list[j] = currElem;
    }
}

void allOnesInsertion() {
    auto data = allOnes.dup;
    data.insertionSort;
    assert(data.isSorted);
}

void sortedInsertion() {
    auto data = sortedData.dup;
    data.insertionSort;
    assert(data.isSorted);
}

void randomInsertion() {
    auto data = randomData.dup;
    data.insertionSort;
    assert(data.isSorted);
}

// HeapSort:

void heapSort(T)(T[] data) {
    auto h = data.heapify;
    while (!h.empty)
        h.removeFront;
}

void allOnesHeap() {
    auto data = allOnes.dup;
    data.heapSort;
    assert(data.isSorted);
}

void sortedHeap() {
    auto data = sortedData.dup;
    data.heapSort;
    assert(data.isSorted);
}

void randomHeap() {
    auto data = randomData.dup;
    data.heapSort;
    assert(data.isSorted);
}

// Built-in sort:

void allOnesBuiltIn() {
    auto data = allOnes.dup;
    data.sort!q{a < b};
    assert(data.isSorted);
}

void sortedBuiltIn() {
    auto data = sortedData.dup;
    data.sort!q{a < b};
    assert(data.isSorted);
}

void randomBuiltIn() {
    auto data = randomData.dup;
    data.sort!q{a < b};
    assert(data.isSorted);
}

static void show(in TickDuration[4u] r) {
    alias args = TypeTuple!("usecs", int);
    writefln("    Bubble Sort:    %10d", r[0].to!args);
    writefln("    Insertion Sort: %10d", r[1].to!args);
    writefln("    Heap Sort:      %10d", r[3].to!args);
    writefln("    Built-in Sort:  %10d", r[2].to!args);
}

void main() {
    enum nRuns = 100;
    writeln("Timings in microseconds:");

    writeln("  Testing against all ones:");
    nRuns.benchmark!(allOnesBubble, allOnesInsertion,
                     allOnesHeap, allOnesBuiltIn).show;

    writeln("\n  Testing against sorted data.");
    nRuns.benchmark!(sortedBubble, sortedInsertion,
                     sortedHeap, sortedBuiltIn).show;

    writeln("\n  Testing against random data.");
    nRuns.benchmark!(randomBubble, randomInsertion,
                     randomHeap, randomBuiltIn).show;
}</syntaxhighlight>
{{out}}
<pre>Timings in microseconds:
  Testing against all ones:
    Bubble Sort:       7377065
    Insertion Sort:       5868
    Heap Sort:           25173
    Built-in Sort:       34538

  Testing against sorted data.
    Bubble Sort:       7370520
    Insertion Sort:       6006
    Heap Sort:           18127
    Built-in Sort:      176235

  Testing against random data.
    Bubble Sort:      27293705
    Insertion Sort:    3762374
    Heap Sort:           85053
    Built-in Sort:      218268</pre>
(With 10,000 elements in each array. A naive HeapSort seems faster than the built-in sort in all three cases.)

=={{header|Erlang}}==
The sort routines are borrowed from [http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort bubble sort], [http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort insertion sort] and [http://rosettacode.org/wiki/Sorting_algorithms/Quicksort quick sort]. Plots by [https://github.com/psyeugenic/eplot eplot].
Bubble sort does [http://github.com/ebengt/rosettacode/tree/master/graphs/ones.png ones] and [http://github.com/ebengt/rosettacode/tree/master/graphs/ranges.png ranges] best. Insertion sort does [http://github.com/ebengt/rosettacode/tree/master/graphs/reversed_ranges.png reversed ranges] best. Quick sort handles [http://github.com/ebengt/rosettacode/tree/master/graphs/shuffleds.png shuffled numbers] best.
<syntaxhighlight lang="erlang">
-module( compare_sorting_algorithms ).

-export( [task/0] ).

task() ->
	Ns = [100, 1000, 10000],
	Lists = [{"ones", fun list_of_ones/1, Ns}, {"ranges", fun list_of_ranges/1, Ns}, {"reversed_ranges", fun list_of_reversed_ranges/1, Ns}, {"shuffleds", fun list_of_shuffleds/1, Ns}],
	Sorts = [{bubble_sort, fun bubble_sort:list/1}, {insertion_sort, fun sort:insertion/1}, {iquick_sort, fun quicksort:qsort/1}],
	Results = [time_list(X, Sorts) || X <- Lists],
	[file:write_file(X++".png", egd_chart:graph(Y, [{x_label,  "log N"}, {y_label, "log ms"}])) || {X, Y} <- Results].


list_of_ones( N ) -> [1 || _X <- lists:seq(1, N)].
list_of_ranges( N ) -> [X || X <- lists:seq(1, N)].
list_of_reversed_ranges( N ) -> lists:reverse( list_of_ranges(N) ).
list_of_shuffleds( N ) -> [random:uniform(N) || _X <- lists:seq(1, N)].

time_list( {List, List_fun, Values}, Sorts ) ->
	Results = [{Sort, time_sort(Sort_fun, List_fun, Values)} || {Sort, Sort_fun} <- Sorts],
	{List, Results}.

time_sort( Sort_fun, List_fun, Values ) ->
	[time(Sort_fun, List_fun, X) || X <- Values].

time( Fun, List_fun, N ) ->
	{Time, _Result} = timer:tc( fun() -> Fun( List_fun(N) ) end ),
	{math:log10(N), math:log10(Time)}.
</syntaxhighlight>

=={{header|Go}}==
{{libheader|gonum/plot}}
<syntaxhighlight lang="go">package main

import (
    "log"
    "math/rand"
    "testing"
    "time"

    "github.com/gonum/plot"
    "github.com/gonum/plot/plotter"
    "github.com/gonum/plot/plotutil"
    "github.com/gonum/plot/vg"
)

// Step 1, sort routines.
// These functions are copied without changes from the RC tasks Bubble Sort,
// Insertion sort, and Quicksort.

func bubblesort(a []int) {
    for itemCount := len(a) - 1; ; itemCount-- {
        hasChanged := false
        for index := 0; index < itemCount; index++ {
            if a[index] > a[index+1] {
                a[index], a[index+1] = a[index+1], a[index]
                hasChanged = true
            }
        }
        if hasChanged == false {
            break
        }
    }
}

func insertionsort(a []int) {
    for i := 1; i < len(a); i++ {
        value := a[i]
        j := i - 1
        for j >= 0 && a[j] > value {
            a[j+1] = a[j]
            j = j - 1
        }
        a[j+1] = value
    }
}

func quicksort(a []int) {
    var pex func(int, int)
    pex = func(lower, upper int) {
        for {
            switch upper - lower {
            case -1, 0:
                return
            case 1:
                if a[upper] < a[lower] {
                    a[upper], a[lower] = a[lower], a[upper]
                }
                return
            }
            bx := (upper + lower) / 2
            b := a[bx]
            lp := lower
            up := upper
        outer:
            for {
                for lp < upper && !(b < a[lp]) {
                    lp++
                }
                for {
                    if lp > up {
                        break outer
                    }
                    if a[up] < b {
                        break
                    }
                    up--
                }
                a[lp], a[up] = a[up], a[lp]
                lp++
                up--
            }
            if bx < lp {
                if bx < lp-1 {
                    a[bx], a[lp-1] = a[lp-1], b
                }
                up = lp - 2
            } else {
                if bx > lp {
                    a[bx], a[lp] = a[lp], b
                }
                up = lp - 1
                lp++
            }
            if up-lower < upper-lp {
                pex(lower, up)
                lower = lp
            } else {
                pex(lp, upper)
                upper = up
            }
        }
    }
    pex(0, len(a)-1)
}

// Step 2.0 sequence routines.  2.0 is the easy part.  2.5, timings, follows.

func ones(n int) []int {
    s := make([]int, n)
    for i := range s {
        s[i] = 1
    }
    return s
}

func ascending(n int) []int {
    s := make([]int, n)
    v := 1
    for i := 0; i < n; {
        if rand.Intn(3) == 0 {
            s[i] = v
            i++
        }
        v++
    }
    return s
}

func shuffled(n int) []int {
    return rand.Perm(n)
}

// Steps 2.5 write timings, and 3 plot timings are coded together.
// If write means format and output human readable numbers, step 2.5
// is satisfied with the log output as the program runs.  The timings
// are plotted immediately however for step 3, not read and parsed from
// any formated output.
const (
    nPts = 7    // number of points per test
    inc  = 1000 // data set size increment per point
)

var (
    p        *plot.Plot
    sortName = []string{"Bubble sort", "Insertion sort", "Quicksort"}
    sortFunc = []func([]int){bubblesort, insertionsort, quicksort}
    dataName = []string{"Ones", "Ascending", "Shuffled"}
    dataFunc = []func(int) []int{ones, ascending, shuffled}
)

func main() {
    rand.Seed(time.Now().Unix())
    var err error
    p, err = plot.New()
    if err != nil {
        log.Fatal(err)
    }
    p.X.Label.Text = "Data size"
    p.Y.Label.Text = "microseconds"
    p.Y.Scale = plot.LogScale{}
    p.Y.Tick.Marker = plot.LogTicks{}
    p.Y.Min = .5 // hard coded to make enough room for legend

    for dx, name := range dataName {
        s, err := plotter.NewScatter(plotter.XYs{})
        if err != nil {
            log.Fatal(err)
        }
        s.Shape = plotutil.DefaultGlyphShapes[dx]
        p.Legend.Add(name, s)
    }
    for sx, name := range sortName {
        l, err := plotter.NewLine(plotter.XYs{})
        if err != nil {
            log.Fatal(err)
        }
        l.Color = plotutil.DarkColors[sx]
        p.Legend.Add(name, l)
    }
    for sx := range sortFunc {
        bench(sx, 0, 1) // for ones, a single timing is sufficient.
        bench(sx, 1, 5) // ascending and shuffled have some randomness though,
        bench(sx, 2, 5) // so average timings on 5 different random sets.
    }

    if err := p.Save(5*vg.Inch, 5*vg.Inch, "comp.png"); err != nil {
        log.Fatal(err)
    }
}

func bench(sx, dx, rep int) {
    log.Println("bench", sortName[sx], dataName[dx], "x", rep)
    pts := make(plotter.XYs, nPts)
    sf := sortFunc[sx]
    for i := range pts {
        x := (i + 1) * inc
        // to avoid timing sequence creation, create sequence before timing
        // then just copy the data inside the timing loop.  copy time should
        // be the same regardless of sequence data.
        s0 := dataFunc[dx](x) // reference sequence
        s := make([]int, x)   // working copy
        var tSort int64
        for j := 0; j < rep; j++ {
            tSort += testing.Benchmark(func(b *testing.B) {
                for i := 0; i < b.N; i++ {
                    copy(s, s0)
                    sf(s)
                }
            }).NsPerOp()
        }
        tSort /= int64(rep)
        log.Println(x, "items", tSort, "ns") // step 2.5, write timings
        pts[i] = struct{ X, Y float64 }{float64(x), float64(tSort) * .001}
    }
    pl, ps, err := plotter.NewLinePoints(pts) // step 3, plot timings
    if err != nil {
        log.Fatal(err)
    }
    pl.Color = plotutil.DarkColors[sx]
    ps.Color = plotutil.DarkColors[sx]
    ps.Shape = plotutil.DefaultGlyphShapes[dx]
    p.Add(pl, ps)
}</syntaxhighlight>
{{out}}
[[file:GoComp.png|right|Comparison]]
Step 4, conclusions about relative performance of the sorting routines made based on the plots.

The plots show differences in best and worse case performance for the various data sets.  Bubble and insertion sorts show very good best case performance with all one and ascending sequences, beating quicksort.  Quicksort shows best case performance with the ascending sequence but worst case performance with the all one sequence.

On random data (triangles) insertion and bubble sort show worse performance than quicksort.
<br clear=all>

=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Time.Clock
import Data.List

type Time = Integer
type Sorter a = [a] -> [a]

-- Simple timing function (in microseconds)
timed :: IO a -> IO (a, Time)
timed prog = do
  t0 <- getCurrentTime
  x <- prog
  t1 <- x `seq` getCurrentTime
  return (x, ceiling $ 1000000 * diffUTCTime t1 t0)
 
-- testing sorting algorithm on a given set
test :: [a] -> Sorter a -> IO [(Int, Time)]
test set srt = mapM (timed . run) ns
  where
    ns = take 15 $ iterate (\x -> (x * 5) `div` 3) 10
    run n = pure $ length $ srt (take n set) 

-- sample sets
constant = repeat 1

presorted = [1..]

random = (`mod` 100) <$> iterate step 42
  where
    step x = (x * a + c) `mod` m
    (a, c, m) = (1103515245, 12345, 2^31-1)</syntaxhighlight>

As a result of testing we get the list of tuples: length of a list and time in microseconds:
<pre>λ> test ones sort
[(10,9),(16,7),(26,5),(43,5),(71,6),(118,8),(196,12),(326,18),(543,28),(905,41),(1508,68),(2513,108),(4188,191),(6980,303),(11633,484)]
λ> test rand sort
[(10,8),(16,7),(26,7),(43,9),(71,15),(118,24),(196,43),(326,82),(543,136),(905,270),(1508,482),(2513,1004),(4188,1926),(6980,4612),(11633,7286)]</pre>

Different sorting methods:

<syntaxhighlight lang="haskell">-- Naive quick sort
qsort :: Ord a => Sorter a
qsort [] = []
qsort (h:t) = qsort (filter (< h) t) ++ [h] ++ qsort (filter (>= h) t)
 
-- Bubble sort
bsort :: Ord a => Sorter a
bsort s = case _bsort s of
               t | t == s    -> t
                 | otherwise -> bsort t
  where _bsort (x:x2:xs) | x > x2    = x2:_bsort (x:xs)
                         | otherwise = x :_bsort (x2:xs)
        _bsort s = s
 
-- Insertion sort
isort :: Ord a => Sorter a
isort = foldr insert []</syntaxhighlight>

Finally, charting routines and the task implementation:
<syntaxhighlight lang="haskell">-- chart appears to be logarithmic scale on both axes
barChart :: Char -> [(Int, Time)] -> [String]
barChart ch lst = bar . scale <$> lst
  where
    scale (x,y) = (x, round $ (3*) $ log $ fromIntegral y)
    bar (x,y) = show x ++ "\t" ++ replicate y ' ' ++ [ch]
 
over :: String -> String -> String
over s1 s2 = take n $ zipWith f (pad s1) (pad s2)
  where
    f ' ' c = c
    f c ' ' = c
    f y _   = y
    pad = (++ repeat ' ')
    n = length s1 `max` length s2

comparison :: Ord a => [Sorter a] -> [Char] -> [a] -> IO ()
comparison sortings chars set = do
  results <- mapM (test set) sortings
  let charts = zipWith barChart chars results
  putStrLn $ replicate 50 '-'
  mapM_ putStrLn $ foldl1 (zipWith over) charts
  putStrLn $ replicate 50 '-'
  let times = map (fromInteger . snd) <$> results
  let ratios = mean . zipWith (flip (/)) (head times) <$> times
  putStrLn "Comparing average time ratios:"
  mapM_ putStrLn $ zipWith (\r s -> [s] ++ ": " ++ show r) ratios chars
  where
    mean lst = sum lst / genericLength lst

main = do
  putStrLn "comparing on list of ones"
  run ones
  putStrLn "\ncomparing on presorted list"
  run seqn
  putStrLn "\ncomparing on shuffled list"
  run rand
  where
    run = comparison [sort, isort, qsort, bsort] "siqb"</syntaxhighlight>

<pre>λ> main
comparing on list of ones
--------------------------------------------------
10	     is b q
16	   is  b   q
26	   s   b     q
43	   si   b      q
71	    si    b       q
118	     si    b         q
196	      si     b           q
326	       si     b            q
543	        s i     b             q
905	          s i    b               q
1508	            s i    b                q
2513	             s  i   b                  q
4188	               s  i   b                   q
6980	                s   i  b                      q
11633	                  s   i  b                       q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.9768226698141058
q: 4948.447011286744
b: 8.648711819912956

comparing on presorted list
--------------------------------------------------
10	      isb  q
16	     s b    q
26	     s b       q
43	     i s b       q
71	      is  b         q
118	       s   b           q
196	        s    b          q
326	         si   b            q
543	          si    b             q
905	            si   b                q
1508	             si    b                q
2513	               si   b                   q
4188	                s i   b                   q
6980	                  s i   b                    q
11633	                    s  i b                       q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.2828547504398033
q: 2586.058542372048
b: 4.478306385307422

comparing on shuffled list
--------------------------------------------------
10	      i  qs
16	      is q  b
26	       s  q    b
43	        is   q      b
71	          s   q      b
118	            si  q        b
196	               si q        b
326	               s    i          b
543	                 s   qi           b
905	                   s     i            b
1508	                     s   q   i          b
2513	                       s    q    i          b
4188	                         s    q      i         b
6980	                          s      q       i         b
11633	                            s       q       i         b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 33.0167854766955
q: 4.778965210071694
b: 920.9348663725772</pre>

We see that well known Haskell meme -- naive quicksort, is total mess on degenerate cases, and it does much better in general, still being significantly more slow then standard implementation. This tests were done in GHCi. Lazy Haskell program may be drastically rewritten and optimized during compilation. Let's see how it goes after compilation:

<pre>$ ghc -O2 CompareSort.hs
[1 of 1] Compiling Main             ( CompareSort.hs, CompareSort.o )
Linking CompareSort ...
$ ./CompareSort
comparing on list of ones
--------------------------------------------------
10	i  q s
16	s  q
26	i  s  q
43	  bs i   q
71	  ibs       q
118	   ibs         q
196	    ib s          q
326	     i bs            q
543	        bis             q
905	        i bs               q
1508	          ib s                q
2513	            ibs                  q
4188	             ib  s                  q
6980	               si                      q
11633	                 si                        q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 0.9148588587463226
q: 751.3527462449417
b: 0.774109602468018

comparing on presorted list
--------------------------------------------------
10	i  s
16	s  q
26	s     q
43	i s      q
71	  s         q
118	   sb          q
196	    is            q
326	     isb             q
543	       sb               q
905	         sb i              q
1508	          is                  q
2513	            sb                   q
4188	              is                    q
6980	                ibs                    q
11633	                  s                        q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.114052564981571
q: 577.8734457264803
b: 1.1171025867573912

comparing on shuffled list
--------------------------------------------------
10	   iqs
16	   is
26	    isb
43	      sq b
71	        si b
118	          si  b
196	            s i  b
326	             sq   i  b
543	               s     i  b
905	                 sq     i   b
1508	                  s q       i  b
2513	                    s q         i  b
4188	                      s q          i  b
6980	                        s  q           i b
11633	                           s  q           i  b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 29.346876854773274
q: 1.3750763918038253
b: 71.47503300525689</pre>

Even though quicksort still sucks on degenerate lists, it does really much better when compiled. Bubble sort had also improved it's rate, in contrast to insertion sort which didn't gain anything from compilation.

=={{header|J}}==
<syntaxhighlight lang="j">
NB. extracts from other rosetta code projects
ts=: 6!:2, 7!:2@]
radix =: 3 : 0
256 radix y
:
a=. #{. z =. x #.^:_1 y
e=. (-a) {."0 b =. i.x
x#.1{::(<:@[;([: ; (b, {"1) <@}./. e,]))&>/^:a [ z;~a-1
NB. , ([: ; (b, {:"1) <@(}:"1@:}.)/. e,])^:(#{.z) y,.z
)
bubble=:  (([ (<. , >.) {.@]) , }.@])/^:_
insertion=:((>: # ]) , [ , < #])/
sel=: 1 : 'x # ['
quick=: 3 : 0
 if.  1 >: #y do.  y
 else.
  e=. y{~?#y
  (quick y <sel e),(y =sel e),quick y >sel e
 end.
)
gaps      =: [: }: 1 (1+3*])^:(> {:)^:a:~ #
insert    =: (I.~ {. ]) , [ , ] }.~ I.~
gapinss   =: #@] {. ,@|:@(] insert//.~ #@] $ i.@[)
shell =: [: ; gapinss &.>/@(< ,~ ]&.>@gaps)
builtin =: /:~



NB. characterization of the sorting algorithms.

sorts =: bubble`insertion`shell`quick`radix`builtin
generators =: #&1`(i.@-)`(?.~) NB. data generators

round =: [: <. 1r2&+

ll =: (<_1 0)&{  NB. verb to extract lower left which holds ln data length
lc =: (<_1 1)&{  NB. verb to fetch lower center which holds most recent time

NB. maximum_time characterize ln_start_size
NB. characterize returns a rank 4 matrix with successive indexes for
NB. algorithm, input arrangement, max number of tests in group, length time space
characterize =: 4 : 0
  max_time =. x
  start =. 1 3{.<:y
  for_sort. sorts do.
    for_generator. generators do.                                           NB. limit time  and  paging prevention
      t =: }. (, (, [: ts 'sort@.0 (generator@.0)' , ":@round@^)@>:@ll) ^: ((lc < max_time"_) *. ll < 17"_) ^:_ start
      if. generator -: {.generators do.
        g =. ,:t
      else.
        g =. g,t
      end.
    end.
    if. sort -: {.sorts do.
      s =. ,:g
    else.
      s =. s,g
    end.
  end.
)

NB. character cell graphics

NB. From j phrases 10E. Approximation
d3=: 1&,.@[ %.~ ]	NB. a and b such that y is approx. a + b*x

NB. domain and range 0 to 14.
D=:14

plot =: 1 : '(=/ round@(u&.(*&(D%<:y))))i.y' NB. function plot size
points =: 4 : '1(<"1|:|.round y*D%~<:x)}0$~2#x'  NB. size points x,:y
   
show =: [: |. [: '0'&~:@{:} ' ' ,: ":

plt =: 3 : 0
30 plt y NB. default size 30
:
n =. >:i.-# experiments =. <@(#~"1 (0&<)@{.)"2 y
pts =. n +./ .*x&points@>experiments
coef =. d3/@>experiments
(_*pts) + n +./ .*1 0 2|:coef&(p."1) plot x
)
</syntaxhighlight>

<pre>
   a =: 1 characterize 5
   $a  NB. a has rank 4
6 3 13 3

   'l t s' =: |:a   NB. transpose moves length time space to leading dimension
   l =: |: <: l     NB. transpose restores order
   t =:	|: 12 +^. t NB. choose arbitrary time units so that ^. time is positive
   s =:	|: ^. s     NB. ln space

   NB. 6 groups of sort methods   with 3 arrangements of data    ---> exponentially increasing data lengths,
   6j2":t   NB. ln time         negative infinity indicates avoided experiment
  3.83  4.80  5.89  7.15  8.65 10.18 11.90 13.75    __    __    __    __    __
  8.77 10.90 13.13    __    __    __    __    __    __    __    __    __    __
  8.70 10.87 13.11    __    __    __    __    __    __    __    __    __    __

  3.91  5.43  7.13  8.90 10.76 12.73    __    __    __    __    __    __    __
  3.99  5.63  7.42  9.21 11.13 13.06    __    __    __    __    __    __    __
  4.14  5.72  7.58  9.37 11.30 13.26    __    __    __    __    __    __    __

  5.56  6.75  7.90  9.05 10.27 11.60 13.13    __    __    __    __    __    __
  5.61  6.88  8.05  9.40 10.84 12.48    __    __    __    __    __    __    __
  5.67  6.93  8.09  9.43 10.89 12.48    __    __    __    __    __    __    __

  1.95  1.99  2.19  2.46  2.98  3.66  4.63  5.54  6.60  7.61  8.70  9.81 10.99
  6.06  7.13  8.09  9.09 10.10 11.10 12.12    __    __    __    __    __    __
  6.09  7.17  8.10  9.11 10.11 11.12 12.14    __    __    __    __    __    __

  3.25  3.33  3.55  4.06  4.77  5.60  6.72  7.75  8.75 10.11 11.21 12.22    __
  3.37  3.87  4.19  4.72  5.53  6.49  7.84  9.29 10.71 11.78 12.88    __    __
  3.42  4.00  4.43  5.07  5.93  7.07  8.06  9.76 10.96 12.10    __    __    __

  0.38  0.38  0.58  1.02  1.68  2.68  3.45  4.42  5.42  6.51  7.64  8.86  9.87
  0.49  0.58  0.96  1.55  2.34  3.11  4.31  5.82  7.43  8.70  9.75 10.75 11.75
  1.40  2.01  2.88  3.87  4.92  5.92  7.05  8.18  9.45 10.91 12.01    __    __
</pre>

This display  is no less than  a bar chart and,  frankly, suffices but
for the curve fit requirement.


<pre>
   NB. algorithms: bubble 6,  insertion 5,  shell 4,  quick 3,  radix 2,  builtin 1
   NB. rows:  log time
   NB. cols:  log size

   NB. data is all 1
   show 30 plt l ,: & (0&{)"2 t
                        5   4 _                       2 2  
                          4                         2      
                      5 _   6                     2        
                    _   4 6                     2          
                      4 _                     _           3
                  5 _   6                   2           3  
                      6                   _       _   3   1
                _ 4                     2         3 3   1  
                _   _                 _         3     1    
              1   6                 2         _   _ 1      
            _                     2         3   1          
            _   _               2 _       _   _            
          4                   2         3   1              
        _ 5   6             2 _     3 _   _                
      4 _   _             2       3     1                  
    _                   _       3 _   _                    
      5   6           2       3     1                      
  4     _           _       3 _   1                        
4   _             2       3     1 _                        
    _ 6       2 _     3 3   1 1                            
  5 6       2       3   _ 1   _                            
          2 _     3 _   1                                  
5 6 _   _       3     1 _                                  
6     2       3 _   1                                      
    2   _   _     1 _                                      
  2 _   3 3     1                                          
2     3       1 _                                          
    3       _                                              
  3 _   _ 1                                                
3     1 1                                                  

   NB. data is  reversed integer list
   show 30 plt l ,: & (1&{)"2 t
          6               4     3                         1
                      5 4     3               2         1  
        _           _ 4     3             _ 2         1    
                    _     3               2         1      
      6             4   _               2         _        
                  1   3               _                    
    _           _   _               2           1          
    6           4 3               _           _            
              1 _               2           1              
  6         _ 3               2           _                
            _               2 _         1                  
6         1               2           _                    
        _ 5             2           1                      
      3               2 _         1                        
    _ 4 _           2             _                        
  3 _                           1                          
3     5           2 _         1                            
  4 _           2           1 _                            
4   5         2 _         1                                
            _           1                                  
  5     _ 2           1 _                                  
5   _   2           1                                      
      2           1 _                                      
    2                                                      
  2             _                                          
2             1                                            
            _                                              
        _ 1                                                
    _   1                                                  
      1                                                    

   NB. data is  random
   show 30 plt l ,: & (2&{)"2 t
          6           5   4     3             2   1        
                    _   4     3             2   1          
        _           5 4     3             2   1            
                    _     3             2   1              
      6           5 4   _             _   _                
                  4   3             2     1                
    _           _   _             _   _ 1                  
    6           4 3                   1                    
              1 _               2   1                      
  6         _ 3               _   _                        
            _               2   1                          
6         1               2   1                            
        _ 5             _   1 _                            
      3 _             2   1                                
    _ 4 5           2   1                                  
  3 _ 5           2 _ 1 _                                  
3 4             2                                          
    _         2 _   _                                      
4           _     1                                        
  5       2     _                                          
        _     1                                            
5   _ 2     _                                              
    2     1                                                
  2     _                                                  
2   _ 1                                                    
    1                                                      
  1                                                        
1                                                          
                                                           
                                                           
</pre>

The first version of the code set only a time limit.  The builtin sort violated this only when the data overflowed RAM into virtual space, causing a large jump in time affecting also the next data set as the OS restored itself.  The timing might be interesting for some other exercise.  Here, a maximum data size test was inserted.  Arbitrary time is the reasonable choice without details of the J interpreter nor of specific hardware.  The radix sort involves putting data directly into the right spot.  It is quick!

The data fit curves of the character cell graph were combined with GCD +. function.  This explains "1"s or other strange values where these curves intersect.  Finally the scatter plots were multiplied by infinity and added to the best fit curves.  The points didn't show up well using the same values as the curves.

=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">
function swap(a, i, j){
    var t = a[i]
    a[i] = a[j]
    a[j] = t
}

// Heap Sort

function heap_sort(a){
    var n = a.length
    
    function heapify(i){
        var t = a[i]
        while (true){
            var l = 2 * i + 1, r = l + 1
            var m = r < n ? (a[l] > a[r] ? l : r) : (l < n ? l : i)
            if (m != i && a[m] > t){
                a[i] = a[m]
                i = m
            }
            else{
                break
            }
        }
        a[i] = t;
    }
    
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--){
        heapify(i)
    }
    
    for (let i = n - 1; i >= 1; i--){
        swap(a, 0, i)
        n--
        heapify(0)
    }
}

// Merge Sort

function merge_sort(a){
    var b = new Array(a.length)
    
    function rec(l, r){
        if (l < r){
            var m = Math.floor((l + r) / 2)
            rec(l, m)
            rec(m + 1, r)
            
            var i = l, j = m + 1, k = 0;

            while (i <= m && j <= r) b[k++] = (a[i] > a[j] ? a[j++] : a[i++])
            while (j <= r) b[k++] = a[j++]
            while (i <= m) b[k++] = a[i++]

            for (k = l; k <= r; k++){
                a[k] = b[k - l]
            }
        }
    }
    
    rec(0, a.length-1)
}

// Quick Sort

function quick_sort(a){
    function rec(l, r){
        if (l < r){
            var p = a[l + Math.floor((r - l + 1)*Math.random())]
            
            var i = l, j = l, k = r
            while (j <= k){
                if (a[j] < p){
                    swap(a, i++, j++)
                }
                else if (a[j] > p){
                    swap(a, j, k--)
                }
                else{
                    j++
                }
            }

            rec(l, i - 1)
            rec(k + 1, r)
        }
    }
    
    rec(0, a.length - 1)
}

// Shell Sort

function shell_sort(a){
    var n = a.length
    var gaps = [100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1]
    
    for (let x of gaps){
        for (let i = x; i < n; i++){
            var t = a[i], j;
            for (j = i; j >= x && a[j - x] > t; j -= x){
                a[j] = a[j - x];
            }
            a[j] = t;
        }
    }
}

// Comb Sort (+ Insertion sort optimization)

function comb_sort(a){
    var n = a.length
    
    for (let x = n; x >= 10; x = Math.floor(x / 1.3)){
        for (let i = 0; i + x < n; i++){
            if (a[i] > a[i + x]){
                swap(a, i, i + x)
            }
        }
    }

    for (let i = 1; i < n; i++){
        var t = a[i], j;
        for (j = i; j > 0 && a[j - 1] > t; j--){
            a[j] = a[j - 1]
        }
        a[j] = t;
    }
}

// Test

function test(f, g, e){
    var res = ""
    
    for (let n of e){
        var a = new Array(n)
        
        var s = 0
        for (let k = 0; k < 10; k++){
            for (let i = 0; i < n; i++){
                a[i] = g(i)
            }
            
            var start = Date.now()
            f(a)
            
            s += Date.now() - start
        }
        
        res += Math.round(s / 10) + "\t"
    }
    
    return res
}

// Main

var e = [5000, 10000, 100000, 500000, 1000000, 2000000]

var sOut = "Test times in ms\n\nElements\t" + e.join("\t") + "\n\n"

sOut += "*All ones*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => 1), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => 1), e) + "\n" 
sOut += "merge_sort\t" + test(merge_sort, (x => 1), e) + "\n" 
sOut += "shell_sort\t" + test(shell_sort, (x => 1), e) + "\n" 
sOut += "comb_sort\t" + test(comb_sort, (x => 1), e) + "\n\n"

sOut += "*Sorted*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => x), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => x), e) + "\n" 
sOut += "merge_sort\t" + test(merge_sort, (x => x), e) + "\n" 
sOut += "shell_sort\t" + test(shell_sort, (x => x), e) + "\n" 
sOut += "comb_sort\t" + test(comb_sort, (x => x), e) + "\n\n"

sOut += "*Random*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => Math.random()), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => Math.random()), e) + "\n" 
sOut += "merge_sort\t" + test(merge_sort, (x => Math.random()), e) + "\n" 
sOut += "shell_sort\t" + test(shell_sort, (x => Math.random()), e) + "\n" 
sOut += "comb_sort\t" + test(comb_sort, (x => Math.random()), e) + "\n"

console.log(sOut)
</syntaxhighlight>
{{out}}
<pre>
Test times in ms

Elements	5000	10000	100000	500000	1000000	2000000

*All ones*
heap_sort	0	0	0	3	5	11	
quick_sort	0	0	0	1	2	4	
merge_sort	1	1	9	50	103	216	
shell_sort	1	0	4	19	39	78	
comb_sort	1	0	6	35	75	160	

*Sorted*
heap_sort	1	1	7	38	79	162	
quick_sort	1	1	10	54	111	230	
merge_sort	1	1	9	50	103	217	
shell_sort	0	0	3	19	39	78	
comb_sort	0	1	6	34	75	160	

*Random*
heap_sort	1	1	12	71	161	383	
quick_sort	1	1	15	85	177	373	
merge_sort	1	1	18	103	215	451	
shell_sort	1	1	15	89	188	397	
comb_sort	1	1	12	74	159	343	
</pre>

=={{header|Julia}}==
Julia comes with the InsertionSort, MergeSort, and QuickSort routines built into the Base.Sort module. Here is a comparison using those system algorithms and with integers.
<syntaxhighlight lang="julia">
function comparesorts(tosort)
    a = shuffle(["i", "m", "q"])
    iavg = mavg = qavg = 0.0
    for c in a
        if c == "i"
            iavg = sum(i -> @elapsed(sort(tosort, alg=InsertionSort)), 1:100) / 100.0
        elseif c == "m"
            mavg = sum(i -> @elapsed(sort(tosort, alg=MergeSort)), 1:100) / 100.0
        elseif c == "q"
            qavg = sum(i -> @elapsed(sort(tosort, alg=QuickSort)), 1:100) / 100.0
        end
    end
    iavg, mavg, qavg
end

allones = fill(1, 40000)
sequential = collect(1:40000)
randomized = collect(shuffle(1:40000))

comparesorts(allones)
comparesorts(allones)
iavg, mavg, qavg = comparesorts(allones)
println("Average sort times for 40000 ones:")
println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")

comparesorts(sequential)
comparesorts(sequential)
iavg, mavg, qavg = comparesorts(sequential)
println("Average sort times for 40000 presorted:")
println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")

comparesorts(randomized)
comparesorts(randomized)
iavg, mavg, qavg = comparesorts(randomized)
println("Average sort times for 40000 randomized:")
println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")
</syntaxhighlight>
<pre>Average sort times for 40000 ones:
        insertion sort: 0.00036058316000000005
        merge sort:     0.00040099004999999996
        quick sort      0.0003586394400000001
Average sort times for 40000 presorted:
        insertion sort: 0.0003141142199999999
        merge sort:     0.0007967360000000003
        quick sort      0.0005601127399999998
Average sort times for 40000 randomized:
        insertion sort: 0.2190664327599999
        merge sort:     0.0028818907399999986
        quick sort      0.0023325933899999997
</pre>

=={{header|Kotlin}}==
This mostly reuses the code from the sorting sub-tasks except that:

1. All sorting functions have been adjusted where necessary so that they sort an IntArray 'in place'. This ensures that the timings are not affected by time spent copying arrays.

2. The bubble sort function, which is very slow when sorting 100,000 random numbers, has been optimized somewhat to try and reduce overall execution time, though the program is still taking about 5 minutes to run on my machine.

Unfortunately the code used to measure CPU time in the 'Time a function' sub-task no longer works properly on my present Windows 10 machine (many results are inexplicably zero). I've therefore had to use the Kotlin library function, measureNanoTime(), instead which measures system time elapsed. Consequently, the results are a bit erratic even when averaged over 10 runs.

Although it would be easy enough to plot the results graphically using an external library such as JFreePlot, there doesn't seem much point when we can no longer upload images to RC. I've therefore presented the results in tabular form on the terminal which is good enough to detect significant trends.
<syntaxhighlight lang="scala">// Version 1.2.31

import java.util.Random
import kotlin.system.measureNanoTime

typealias Sorter = (IntArray) -> Unit

val rand = Random()

fun onesSeq(n: Int) = IntArray(n) { 1 }

fun ascendingSeq(n: Int) = shuffledSeq(n).sorted().toIntArray()

fun shuffledSeq(n: Int) = IntArray(n) { 1 + rand.nextInt(10 * n) }

fun bubbleSort(a: IntArray) {
    var n = a.size
    do {
        var n2 = 0
        for (i in 1 until n) {
            if (a[i - 1] > a[i]) {
                val tmp = a[i]
                a[i] = a[i - 1]
                a[i - 1] = tmp
                n2 = i
            }
        }
        n = n2
    } while (n != 0)
}

fun insertionSort(a: IntArray) {
    for (index in 1 until a.size) {
        val value = a[index]
        var subIndex = index - 1
        while (subIndex >= 0 && a[subIndex] > value) {
            a[subIndex + 1] = a[subIndex]
            subIndex--
        }
        a[subIndex + 1] = value
    }
}

fun quickSort(a: IntArray) {
    fun sorter(first: Int, last: Int) {
        if (last - first < 1) return
        val pivot = a[first + (last - first) / 2]
        var left = first
        var right = last
        while (left <= right) {
            while (a[left] < pivot) left++
            while (a[right] > pivot) right--
            if (left <= right) {
                val tmp = a[left]
                a[left] = a[right]
                a[right] = tmp
                left++
                right--
            }
        }
        if (first < right) sorter(first, right)
        if (left < last) sorter(left, last)
    }
    sorter(0, a.lastIndex)
}

fun radixSort(a: IntArray) {
    val tmp = IntArray(a.size)
    for (shift in 31 downTo 0) {
        tmp.fill(0)
        var j = 0
        for (i in 0 until a.size) {
            val move = (a[i] shl shift) >= 0
            val toBeMoved = if (shift == 0) !move else move
            if (toBeMoved)
                tmp[j++] = a[i]
            else {
                a[i - j] = a[i]
            }
        }
        for (i in j until tmp.size) tmp[i] = a[i - j]
        for (i in 0 until a.size) a[i] = tmp[i]
    }
}

val gaps = listOf(701, 301, 132, 57, 23, 10, 4, 1)  // Marcin Ciura's gap sequence

fun shellSort(a: IntArray) {
    for (gap in gaps) {
        for (i in gap until a.size) {
            val temp = a[i]
            var j = i
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap]
                j -= gap
            }
            a[j] = temp
        }
    }
}

fun main(args: Array<String>) {
    val runs = 10
    val lengths = listOf(1, 10, 100, 1_000, 10_000, 100_000)
    val sorts = listOf<Sorter>(
        ::bubbleSort, ::insertionSort, ::quickSort, ::radixSort, ::shellSort
    )

    /* allow JVM to compile sort functions before timings start */
    for (sort in sorts) sort(intArrayOf(1))

    val sortTitles = listOf("Bubble", "Insert", "Quick ", "Radix ", "Shell ")
    val seqTitles = listOf("All Ones", "Ascending", "Shuffled")
    val totals = List(seqTitles.size) { List(sorts.size) { LongArray(lengths.size) } }
    for ((k, n) in lengths.withIndex()) {
        val seqs = listOf(onesSeq(n), ascendingSeq(n), shuffledSeq(n))
        repeat(runs) {
            for (i in 0 until seqs.size) {           
                for (j in 0 until sorts.size) {
                    val seq = seqs[i].copyOf()
                    totals[i][j][k] += measureNanoTime { sorts[j](seq) }
                }
            }
        }
    }
    println("All timings in micro-seconds\n")
    print("Sequence length")
    for (len in lengths) print("%8d   ".format(len))
    println("\n")
    for (i in 0 until seqTitles.size) {
        println("  ${seqTitles[i]}:")
        for (j in 0 until sorts.size) {
            print("    ${sortTitles[j]}     ")
            for (k in 0 until lengths.size) {
                val time = totals[i][j][k] / runs / 1_000
                print("%8d   ".format(time))
            }
            println()
        }
        println("\n")
    }
}</syntaxhighlight>

{{out}}
<pre>
All timings in micro-seconds

Sequence length       1         10        100       1000      10000     100000

  All Ones:
    Bubble            1          2          6         24         26        264
    Insert            1         16         10         14         48        518
    Quick             2          7         18         46        397       5181
    Radix            38         79        501       3720        864       9096
    Shell            11         15         43        189        407       4105


  Ascending:
    Bubble            1          2          6          8         24        270
    Insert            0          2          9         14         47        496
    Quick             1          6         19         33        282       3347
    Radix            38         71        264        415       1869      21403
    Shell             7         10         42        171        399       4052


  Shuffled:
    Bubble            1          5        436       3292     275224   27730705
    Insert            0          3        176        754      24759    2546180
    Quick             1          7         24        106       1281      14982
    Radix            28         73        622        317       1891      21617
    Shell            11         19         88        408       1946      36980
</pre>

===Conclusions===
As expected quick sort is faster than the other methods when applied to random data of a reasonable size though radix and shell sort are also respectable performers for large amounts of random data. In contrast, bubble and insertion sorts are orders of magnitude slower, particularly the former.

On the other hand, bubble and insertion sorts are much quicker than the other methods for constant data and for data which is already sorted in an ascending direction, bubble sort being the faster of the two.

=={{header|Mathematica}}/{{header|Wolfram Language}}==
Comparing bubble and shell sort:
<syntaxhighlight lang="mathematica">ClearAll[BubbleSort,ShellSort]
BubbleSort[in_List]:=Module[{x=in,l=Length[in],swapped},swapped=True;
 While[swapped,swapped=False;
 Do[If[x[[i]]>x[[i+1]],x[[{i,i+1}]]//=Reverse;
 swapped=True;],{i,l-1}];];
x]
ShellSort[lst_]:=Module[{list=lst,incr,temp,i,j},incr=Round[Length[list]/2];
 While[incr>0,For[i=incr+1,i<=Length[list],i++,temp=list[[i]];j=i;
 While[(j>=(incr+1))&&(list[[j-incr]]>temp),list[[j]]=list[[j-incr]];j=j-incr;];
 list[[j]]=temp;];
 If[incr==2,incr=1,incr=Round[incr/2.2]]];list
]

times=Table[
 arr=ConstantArray[1,n];
 t1={{n,AbsoluteTiming[BubbleSort[arr];][[1]]},{n,AbsoluteTiming[ShellSort[arr];][[1]]}};
 arr=Sort[RandomInteger[{10^6},n]];
 t2={{n,AbsoluteTiming[BubbleSort[arr];][[1]]},{n,AbsoluteTiming[ShellSort[arr];][[1]]}};
 arr=RandomInteger[{10^6},n];
 t3={{n,AbsoluteTiming[BubbleSort[arr];][[1]]},{n,AbsoluteTiming[ShellSort[arr];][[1]]}};
 {t1,t2,t3}
,
 {n,2^Range[13]}
];

ListLogLogPlot[Transpose@times[[All,1]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ones"]
ListLogLogPlot[Transpose@times[[All,2]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ascending integers"]
ListLogLogPlot[Transpose@times[[All,3]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Shuffled"]</syntaxhighlight>
{{out}}
Outputs three graphs on a log-log scales showing the size of the array and the time taken, for each of the three different arrays.

=={{header|Nim}}==
{{trans|Kotlin}}

This is a direct translation of the Kotlin program. We have added the sorting algorithm provided by Nim standard library which is a merge sort. For this reason, we have been constrained to annotate the sorting functions with the pragma {.locks: "unknown".} to make their type compatible with that of the standard sort function.

We have also added the array as first parameter of the internal function “sorter” as Nim compiler doesn’t allow direct access to this mutable array in function “quicksort” (memory safety violation).

<syntaxhighlight lang="nim">import algorithm
import random
import sequtils
import times


####################################################################################################
# Data.

proc oneSeq(n: int): seq[int] = repeat(1, n)

#---------------------------------------------------------------------------------------------------

proc shuffledSeq(n: int): seq[int] =
  result.setLen(n)
  for item in result.mitems: item = rand(1..(10 * n))

#---------------------------------------------------------------------------------------------------

proc ascendingSeq(n: int): seq[int] = sorted(shuffledSeq(n))


####################################################################################################
# Algorithms.

func bubbleSort(a: var openArray[int]) {.locks: "unknown".} =
  var n = a.len
  while true:
    var n2 = 0
    for i in 1..<n:
      if a[i - 1] > a[i]:
        swap a[i], a[i - 1]
        n2 = i
    n = n2
    if n == 0: break

#---------------------------------------------------------------------------------------------------

func insertionSort(a: var openArray[int]) {.locks: "unknown".} =
  for index in 1..a.high:
    let value = a[index]
    var subIndex = index - 1
    while subIndex >= 0 and a[subIndex] > value:
      a[subIndex + 1] = a[subIndex]
      dec subIndex
    a[subIndex + 1] = value

#---------------------------------------------------------------------------------------------------

func quickSort(a: var openArray[int]) {.locks: "unknown".} =

  func sorter(a: var openArray[int]; first, last: int) =
    if last - first < 1: return
    let pivot = a[first + (last - first) div 2]
    var left = first
    var right = last
    while left <= right:
      while a[left] < pivot: inc left
      while a[right] > pivot: dec right
      if left <= right:
        swap a[left], a[right]
        inc left
        dec right
    if first < right: a.sorter(first, right)
    if left < last: a.sorter(left, last)

  a.sorter(0, a.high)

#---------------------------------------------------------------------------------------------------

func radixSort(a: var openArray[int]) {.locks: "unknown".} =

  var tmp = newSeq[int](a.len)

  for shift in countdown(63, 0):
    for item in tmp.mitems: item = 0
    var j = 0
    for i in 0..a.high:
      let move = a[i] shl shift >= 0
      let toBeMoved = if shift == 0: not move else: move
      if toBeMoved:
        tmp[j] = a[i]
        inc j
      else:
        a[i - j] = a[i]
    for i in j..tmp.high: tmp[i] = a[i - j]
    for i in 0..a.high: a[i] = tmp[i]

#---------------------------------------------------------------------------------------------------

func shellSort(a: var openArray[int]) {.locks: "unknown".} =

  const Gaps = [701, 301, 132, 57, 23, 10, 4, 1]

  for gap in Gaps:
    for i in gap..a.high:
      let temp = a[i]
      var j = i
      while j >= gap and a[j - gap] > temp:
        a[j] = a[j - gap]
        dec j, gap
      a[j] = temp

#---------------------------------------------------------------------------------------------------

func standardSort(a: var openArray[int]) =
  a.sort()


####################################################################################################
# Main code.

import strformat

const

  Runs = 10
  Lengths = [1, 10, 100, 1_000, 10_000, 100_000]

  Sorts = [bubbleSort, insertionSort, quickSort, radixSort, shellSort, standardSort]

const
  SortTitles = ["Bubble", "Insert", "Quick ", "Radix ", "Shell ", "Standard"]
  SeqTitles = ["All Ones", "Ascending", "Shuffled"]

var totals: array[SeqTitles.len, array[Sorts.len, array[Lengths.len, Duration]]]

randomize()

for k, n in Lengths:
  let seqs = [oneSeq(n), ascendingSeq(n), shuffledSeq(n)]
  for _ in 1..Runs:
    for i, s in seqs:
      for j, sort in Sorts:
        var s = s
        let t0 = getTime()
        s.sort()
        totals[i][j][k] += getTime() - t0

echo "All timings in microseconds\n"
stdout.write "Sequence length  "
for length in Lengths:
  stdout.write &"{length:6d}     "
echo '\n'
for i in 0..SeqTitles.high:
  echo &"  {SeqTitles[i]}:"
  for j in 0..Sorts.high:
    stdout.write &"  {SortTitles[j]:8s}     "
    for k in 0..Lengths.high:
      let time = totals[i][j][k].inMicroseconds div Runs
      stdout.write &"{time:8d}   "
    echo ""
  echo '\n'</syntaxhighlight>

{{out}}
<pre>All timings in microseconds

Sequence length       1         10        100       1000      10000     100000     

  All Ones:
  Bubble              0          0          0          0          6         64   
  Insert              0          0          0          1          9         90   
  Quick               0          0          3          9        105       1201   
  Radix               1          4         34        103        848       8354   
  Shell               0          0          2         10         97        946   
  Standard            0          2          2          6         45        380   


  Ascending:
  Bubble              0          0          0          0          6         61   
  Insert              0          0          0          1          9         94   
  Quick               0          0          3         11         88        919   
  Radix               1          5         47        154       1435      15519   
  Shell               0          0          2         10         95        954   
  Standard            0          0          2          7         47        463   


  Shuffled:
  Bubble              0          0         38       1026     133729   16181412   
  Insert              0          0          8        152      10010    1133210   
  Quick               0          0          9         63        607       7199   
  Radix               1          5         46        157       1405      15557   
  Shell               0          0          8         69        708      10236   
  Standard            0          0         18         96        992      12394</pre>

===Conclusions===

Compared to the results obtained by the Kotlin program, the radix sort seems less efficient and the shell sort more efficient. Maybe some optimizations could improve the radix sort, but it seems also that the shell sort is well optimized by the Nim compiler and the C compiler.

The standard sort behaves well if the list is already sorted. For random list, it is less efficient than the quick sort or the shell sort, but is still a good performer.

=={{header|Phix}}==
{{libheader|Phix/pGUI}}
<!--<syntaxhighlight lang="phix">-->
 <span style="color: #000080;font-style:italic;">-- demo\rosetta\Compare_sorting_algorithms.exw</span>
 <span style="color: #008080;">constant</span> <span style="color: #000000;">XQS</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">01</span>  <span style="color: #000080;font-style:italic;">-- (set to 1 to exclude quick_sort and shell_sort from ones)</span>
  
 <span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
  
 <span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">plot</span>
 <span style="color: #004080;">Ihandles</span> <span style="color: #000000;">plots</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
         <span style="color: #008080;">return</span> <span style="color: #000000;">x</span>    <span style="color: #000080;font-style:italic;">-- already sorted (trivial case)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
             <span style="color: #000000;">midn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
     <span style="color: #004080;">object</span>  <span style="color: #000000;">midval</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
     <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">object</span> <span style="color: #000000;">xi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">midval</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
             <span style="color: #000000;">left</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">elsif</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
             <span style="color: #000000;">right</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xi</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">else</span>
             <span style="color: #000000;">midn</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
  
     <span style="color: #008080;">return</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">&</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">midval</span><span style="color: #0000FF;">,</span><span style="color: #000000;">midn</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">quick_sort2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right</span><span style="color: #0000FF;">)</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">quick_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">qstack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</span>   <span style="color: #000080;font-style:italic;">-- create a stack</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
             <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span>
             <span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
     <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">while</span> <span style="color: #000000;">first</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
             <span style="color: #004080;">object</span> <span style="color: #000000;">pivot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">last</span><span style="color: #0000FF;">+</span><span style="color: #000000;">first</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
                    <span style="color: #000000;">si</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sj</span>
             <span style="color: #004080;">integer</span> <span style="color: #000000;">I</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">first</span><span style="color: #0000FF;">,</span>
                     <span style="color: #000000;">J</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span>
             <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
                 <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
                     <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span>
                     <span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">pivot</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                     <span style="color: #000000;">I</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
                 <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
                     <span style="color: #000000;">sj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">J</span><span style="color: #0000FF;">]</span>
                     <span style="color: #008080;">if</span> <span style="color: #000000;">sj</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">pivot</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                     <span style="color: #000000;">J</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">></span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;"><</span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span>
                     <span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sj</span> <span style="color: #008080;">then</span>
                         <span style="color: #0000FF;">{</span><span style="color: #000000;">I</span><span style="color: #0000FF;">,</span><span style="color: #000000;">J</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">J</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">I</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
                         <span style="color: #008080;">exit</span>
                     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                     <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">I</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sj</span>
                     <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">J</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                 <span style="color: #000000;">I</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
                 <span style="color: #000000;">J</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;">></span><span style="color: #000000;">J</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
             <span style="color: #008080;">if</span> <span style="color: #000000;">I</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">then</span>
                 <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">I</span>
                 <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span>
                 <span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">J</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">stackptr</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #000000;">stackptr</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">2</span>
         <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
         <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">qstack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">stackptr</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
         <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
             <span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
                 <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
             <span style="color: #008080;">else</span>
                 <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{},{}}</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
             <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],-</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">else</span>
             <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">buckets</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">radix_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
 <span style="color: #000080;font-style:italic;">-- NB this is an integer-only sort</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">mins</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span>
             <span style="color: #000000;">passes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">log10</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mins</span><span style="color: #0000FF;">))))+</span><span style="color: #000000;">1</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">mins</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
         <span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sq_uminus</span><span style="color: #0000FF;">(</span><span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)))</span>
         <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
     <span style="color: #008080;">else</span>
         <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">shell_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">while</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">gap</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
             <span style="color: #004080;">object</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
             <span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">gap</span>
             <span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">temp</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
                 <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
                 <span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">gap</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
             <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">shell_sort2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">),</span>
             <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">last</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
     <span style="color: #008080;">while</span> <span style="color: #004600;">TRUE</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">first</span> <span style="color: #008080;">to</span> <span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
             <span style="color: #004080;">object</span> <span style="color: #000000;">xi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
             <span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">gap</span>
             <span style="color: #008080;">while</span> <span style="color: #004600;">TRUE</span> <span style="color: #008080;">do</span>
                 <span style="color: #004080;">object</span> <span style="color: #000000;">xj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">xi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">xj</span> <span style="color: #008080;">then</span>
                     <span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span>
                     <span style="color: #008080;">exit</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                 <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xj</span>
                 <span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">gap</span> <span style="color: #008080;">then</span>
                     <span style="color: #008080;">exit</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
                 <span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">gap</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
             <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xi</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
             <span style="color: #008080;">return</span> <span style="color: #000000;">x</span>
         <span style="color: #008080;">else</span>
             <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3.5</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
     <span style="color: #008080;">while</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">last</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">child</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">root</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">child</span><span style="color: #0000FF;"><</span><span style="color: #000000;">last</span> <span style="color: #008080;">and</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
             <span style="color: #000000;">child</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]>=</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span>
         <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">root</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span>
         <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">child</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span>
         <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">child</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">while</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
         <span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">s</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span>
     <span style="color: #004080;">integer</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">)</span>
     <span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">heapify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">while</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">object</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
         <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span>
         <span style="color: #000000;">arr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span>
         <span style="color: #000000;">last</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
         <span style="color: #000000;">arr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">siftDown</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
     <span style="color: #008080;">return</span> <span style="color: #000000;">arr</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">/</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
  
 <span style="color: #008080;">enum</span> <span style="color: #000000;">ONES</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">SORTED</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RANDOM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">REVERSE</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
  
 <span style="color: #008080;">constant</span> <span style="color: #000000;">tabtitles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"ones"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sorted"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"random"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"reverse"</span><span style="color: #0000FF;">}</span>
 <span style="color: #004080;">integer</span> <span style="color: #000000;">tabidx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span>
  
 <span style="color: #004080;">integer</span> <span style="color: #000000;">STEP</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #000000;">name</span><span style="color: #0000FF;">))</span>
     <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">name</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rid</span><span style="color: #0000FF;">}</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"quick_sort"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"quick_sort2"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"radix_sort"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"shell_sort"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"shell_sort2"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"heap_sort"</span><span style="color: #0000FF;">),</span>
                   <span style="color: #000000;">tr</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"sort"</span><span style="color: #0000FF;">),</span>           <span style="color: #000080;font-style:italic;">-- builtin</span>
                  <span style="color: #0000FF;">}</span>
  
 <span style="color: #004080;">sequence</span> <span style="color: #000000;">results</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">))</span>
  
 <span style="color: #004080;">sequence</span> <span style="color: #000000;">dsdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">))</span>
  
 <span style="color: #004080;">integer</span> <span style="color: #000000;">ds_index</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">idle_action_cb</span><span style="color: #0000FF;">()</span>
     <span style="color: #004080;">atom</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- fastest last</span>
          <span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1..length(tests) </span>
          <span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- 1..length(tabtitles)</span>
          <span style="color: #000000;">len</span>
     <span style="color: #000080;font-style:italic;">--
     -- Search for something to do, active/visible tab first.
     -- Any result set of length 0 -&gt; just do one.
     -- Of all result sets&lt;8, pick the lowest [$].
     --</span>
     <span style="color: #004080;">sequence</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tabidx</span><span style="color: #0000FF;">}</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">tabidx</span> <span style="color: #008080;">then</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
  
     <span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #004080;">integer</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">todo</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">]</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
             <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
             <span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
                 <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
                 <span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
                 <span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ti</span>
                 <span style="color: #008080;">exit</span>
             <span style="color: #008080;">elsif</span> <span style="color: #000000;">len</span><span style="color: #0000FF;"><</span><span style="color: #000000;">8</span> <span style="color: #008080;">then</span>
                 <span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">></span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][$])</span> <span style="color: #008080;">then</span>
                     <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][$]</span>
                     <span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
                     <span style="color: #000000;">bestt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ti</span>
                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">></span><span style="color: #000000;">10</span> <span style="color: #008080;">then</span>
         <span style="color: #000080;font-style:italic;">-- cop out if it is getting too slow</span>
         <span style="color: #000000;">besti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #008080;">if</span> <span style="color: #000000;">besti</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
         <span style="color: #000000;">STEP</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #008080;">not</span> <span style="color: #000000;">XQS</span> <span style="color: #008080;">and</span> <span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">:</span><span style="color: #000000;">100000</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">STEP</span>
         <span style="color: #004080;">sequence</span> <span style="color: #000000;">test</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">):</span>
                         <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">SORTED</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">):</span>
                         <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">RANDOM</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)):</span>
                         <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">REVERSE</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)):</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span><span style="color: #0000FF;">))))</span>
         <span style="color: #000000;">ds_index</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dsdx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">]</span>
         <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
         <span style="color: #004080;">sequence</span> <span style="color: #000000;">check</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">call_func</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">test</span><span style="color: #0000FF;">})</span>
         <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
 <span style="color: #000080;font-style:italic;">--      if check!=sort(test) then ?9/0 end if</span>
         <span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">plots</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">]</span>
         <span style="color: #7060A8;">IupPlotInsert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ds_index</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
         <span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">besti</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"REDRAW"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span>
         <span style="color: #004080;">sequence</span> <span style="color: #7060A8;">progress</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">}</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
             <span style="color: #7060A8;">progress</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bestt</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #7060A8;">IupSetStrAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Compare sorting algorithms %s"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">progress</span><span style="color: #0000FF;">)})</span>
         <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_CONTINUE</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
     <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Compare sorting algorithms (all done, idle)"</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_IGNORE</span>   <span style="color: #000080;font-style:italic;">-- all done, remove callback</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 <span style="color: #008080;">constant</span> <span style="color: #000000;">cb_idle_action</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"idle_action_cb"</span><span style="color: #0000FF;">)</span>
  
 <span style="color: #008080;">function</span> <span style="color: #000000;">tabchange_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*self*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*new_tab*/</span><span style="color: #0000FF;">)</span>
     <span style="color: #000000;">tabidx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupGetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"VALUEPOS"</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
     <span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">plots</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tabidx</span><span style="color: #0000FF;">]</span>
     <span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span><span style="color: #0000FF;">;</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  
 <span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
     <span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span>
  
     <span style="color: #000000;">plots</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
     <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
         <span style="color: #008080;">if</span> <span style="color: #000000;">XQS</span> <span style="color: #008080;">then</span>
 <span style="color: #000080;font-style:italic;">--          results[ONES][1] = repeat(0,8)</span>
             <span style="color: #000000;">results</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ONES</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
         <span style="color: #000000;">plot</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlot</span><span style="color: #0000FF;">()</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MENUITEMPROPERTIES"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TABTITLE"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tabtitles</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"GRID"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MARGINLEFT"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"50"</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MARGINBOTTOM"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"40"</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"LEGEND"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"YES"</span><span style="color: #0000FF;">)</span>
         <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"LEGENDPOS"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TOPLEFT"</span><span style="color: #0000FF;">)</span>
 <span style="color: #000080;font-style:italic;">--      IupSetAttribute(plot,"AXS_YSCALE","LOG10")
 --      IupSetAttribute(plot,"AXS_XSCALE","LOG10")</span>
         <span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
             <span style="color: #7060A8;">IupPlotBegin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
             <span style="color: #000000;">dsdx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupPlotEnd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
             <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DS_NAME"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
         <span style="color: #000000;">plots</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plots</span><span style="color: #0000FF;">,</span><span style="color: #000000;">plot</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
     <span style="color: #000000;">tabs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupTabs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plots</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">IupSetCallback</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TABCHANGE_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"tabchange_cb"</span><span style="color: #0000FF;">))</span>
     <span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RASTERSIZE=800x480"</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"TITLE"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"Compare sorting algorithms"</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">IupSetInt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tabs</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"VALUEPOS"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tabidx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
     <span style="color: #7060A8;">IupSetGlobalFunction</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"IDLE_ACTION"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cb_idle_action</span><span style="color: #0000FF;">)</span>
     <span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
         <span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span>
         <span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
  
 <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
===Conclusions===
I knew bubblesort and insertion sort would be bad, but not so bad that you cannot meaningfully plot them against better sorts.
(logarithmic scale helps, but is still not enough)
I had no idea that (these particular implementations of) quicksort and shellsort would be so bad on a sequence of all 1s.
(so bad in fact that I had to cap that test length to 8,000 instead of 800,000 as used for the other tests)
The builtin sort and shell_sort2 were the clear winners, until I found a non-recursive quicksort that seems quite good.
IupPlot is brilliant! It is actually quite fun to watch the graphs grow as you get more results in!
There is a point where you realise you are currently wasting your life fretting over 0.015 seconds...

The ultimate conclusion is, of course, that there are some differences, but as long as you weed out the really bad
algorithms, and at least in the majority of cases, you will probably never notice whether sorting 800,000 items 
takes 0.25s or 0.1s - more significant gains are likely to be found elsewhere.

=={{header|Python}}==
{{works with|Python|2.5}}
===Examples of sorting routines=== 
<syntaxhighlight lang="python">def builtinsort(x):
    x.sort()

def partition(seq, pivot):
   low, middle, up = [], [], []
   for x in seq:
       if x < pivot:
           low.append(x)
       elif x == pivot:
           middle.append(x)
       else:
           up.append(x)
   return low, middle, up
import random
def qsortranpart(seq):
   size = len(seq)
   if size < 2: return seq
   low, middle, up = partition(seq, random.choice(seq))
   return qsortranpart(low) + middle + qsortranpart(up)</syntaxhighlight>

===Sequence generators===

<syntaxhighlight lang="python">def ones(n):
    return [1]*n

def reversedrange(n):
    return reversed(range(n))

def shuffledrange(n):
    x = range(n)
    random.shuffle(x)
    return x</syntaxhighlight>    
===Write timings===
<syntaxhighlight lang="python">def write_timings(npoints=10, maxN=10**4, sort_functions=(builtinsort,insertion_sort, qsort), 
                  sequence_creators = (ones, range, shuffledrange)):    
   Ns = range(2, maxN, maxN//npoints)
   for sort in sort_functions:
       for make_seq in sequence_creators:
           Ts = [usec(sort, (make_seq(n),)) for n in Ns]
           writedat('%s-%s-%d-%d.xy' % (sort.__name__,  make_seq.__name__, len(Ns), max(Ns)), Ns, Ts)</syntaxhighlight>
Where ''writedat()'' is defined in the [[Write float arrays to a text file]], ''usec()'' - [[Query Performance]], ''insertion_sort()'' - [[Insertion sort]], ''qsort'' - [[Quicksort]] subtasks, correspondingly.

===Plot timings===
{{libheader|matplotlib}}
{{libheader|NumPy}}
<syntaxhighlight lang="python">import operator
import numpy, pylab
def plotdd(dictplotdict):
   """See ``plot_timings()`` below."""
   symbols = ('o', '^', 'v', '<', '>', 's', '+', 'x', 'D', 'd',
              '1', '2', '3', '4', 'h', 'H', 'p', '|', '_')
   colors = list('bgrcmyk') # split string on distinct characters
   for npoints, plotdict in dictplotdict.iteritems():
       for ttle, lst in plotdict.iteritems():            
           pylab.hold(False)                                
           for i, (label, polynom, x, y) in enumerate(sorted(lst,key=operator.itemgetter(0))):
               pylab.plot(x, y, colors[i % len(colors)] + symbols[i % len(symbols)], label='%s %s' % (polynom, label))
               pylab.hold(True)
               y = numpy.polyval(polynom, x)
               pylab.plot(x, y, colors[i % len(colors)], label= '_nolegend_')                
           pylab.legend(loc='upper left')
           pylab.xlabel(polynom.variable)
           pylab.ylabel('log2( time in microseconds )')                
           pylab.title(ttle, verticalalignment='bottom')
           figname = '_%(npoints)03d%(ttle)s' % vars()
           pylab.savefig(figname+'.png')
           pylab.savefig(figname+'.pdf')
           print figname</syntaxhighlight>
See [[Plot x, y arrays]] and [[Polynomial Fitting]] subtasks for a basic usage of ''pylab.plot()'' and ''numpy.polyfit()''.

<syntaxhighlight lang="python">import collections, itertools, glob, re
import numpy
def plot_timings():
   makedict = lambda: collections.defaultdict(lambda: collections.defaultdict(list))
   df = makedict()
   ds = makedict()
   # populate plot dictionaries
   for filename in glob.glob('*.xy'):
       m = re.match(r'([^-]+)-([^-]+)-(\d+)-(\d+)\.xy', filename)
       print filename
       assert m, filename
       funcname, seqname, npoints, maxN = m.groups()
       npoints, maxN = int(npoints), int(maxN)        
       a = numpy.fromiter(itertools.imap(float, open(filename).read().split()), dtype='f')
       Ns = a[::2]  # sequences lengths
       Ts = a[1::2] # corresponding times 
       assert len(Ns) == len(Ts) == npoints
       assert max(Ns) <= maxN
       #
       logsafe = numpy.logical_and(Ns>0, Ts>0)
       Ts = numpy.log2(Ts[logsafe])
       Ns = numpy.log2(Ns[logsafe])
       coeffs = numpy.polyfit(Ns, Ts, deg=1)
       poly = numpy.poly1d(coeffs, variable='log2(N)')
       #
       df[npoints][funcname].append((seqname, poly, Ns, Ts))
       ds[npoints][seqname].append((funcname, poly, Ns, Ts))
   # actual plotting
   plotdd(df)
   plotdd(ds) # see ``plotdd()`` above</syntaxhighlight>

===Figures: log2( time in microseconds ) vs. log2( sequence length )=== 
[[File:Ones.png|300px|thumb|right|log(Time) vs. log(N): Relative performance on [1]*N as an input]]
[[File:Range.png|300px|thumb|right|log(Time) vs. log(N): Relative performance on range(N) as an input]]
[[File:Shuffledrange.png|300px|thumb|right|log(Time) vs. log(N): Relative performance on random permutation of range(N) as an input]]
<syntaxhighlight lang="python">sort_functions = [
    builtinsort,         # see implementation above
    insertion_sort,      # see [[Insertion sort]]
    insertion_sort_lowb, # ''insertion_sort'', where sequential search is replaced
                         #     by lower_bound() function
    qsort,               # see [[Quicksort]]
    qsortranlc,          # ''qsort'' with randomly choosen ''pivot''
                         #     and the filtering via list comprehension
    qsortranpart,        # ''qsortranlc'' with filtering via ''partition'' function
    qsortranpartis,      # ''qsortranpart'', where for a small input sequence lengths
    ]                    #     ''insertion_sort'' is called
if __name__=="__main__":
   import sys
   sys.setrecursionlimit(10000)
   write_timings(npoints=100, maxN=1024, # 1 <= N <= 2**10 an input sequence length
                 sort_functions=sort_functions,
                 sequence_creators = (ones, range, shuffledrange))
   plot_timings()</syntaxhighlight>
Executing above script we get belowed figures.
====ones====
[http://i28.tinypic.com/5lcfmo.png ones.png] (143KiB)

 builtinsort     - O(N)
 insertion_sort  - O(N)
 qsort           - O(N**2)
 qsortranpart    - O(N)

====range====
[http://i32.tinypic.com/14azio6.png range.png] (145KiB)
 builtinsort     - O(N)
 insertion_sort  - O(N)
 qsort           - O(N**2)
 qsortranpart    - O(N*log(N))

====shuffled range====
[http://i28.tinypic.com/juclyu.png shuffledrange.png] (152KiB)
 builtinsort     - O(N)  
 insertion_sort  - O(N**4) ???
 qsort           - O(N*log(N))
 qsortranpart    - O(N) ???

=={{header|Raku}}==
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20221114 Raku programming solution

my ($rounds,$size) = 3, 2000;
my @allones        = 1 xx $size;
my @sequential     = 1 .. $size;
my @randomized     = @sequential.roll xx $size; 

sub insertion_sort ( @a is copy ) { # rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#Raku
   for 1 .. @a.end -> \k {
      loop (my ($j,\value)=k-1,@a[k];$j>-1&&@a[$j]>value;$j--) {@a[$j+1]=@a[$j]}
      @a[$j+1] = value;
   }
   return @a;
}

sub merge_sort ( @a ) { # rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Raku
    return @a if @a <= 1;

    my $m = @a.elems div 2;
    my @l = merge_sort @a[  0 ..^ $m ];
    my @r = merge_sort @a[ $m ..^ @a ];

    return flat @l, @r if @l[*-1] !after @r[0];
    return flat gather {
        take @l[0] before @r[0] ?? @l.shift !! @r.shift
            while @l and @r;
        take @l, @r;
    }
}

sub quick-sort(@data) { # andrewshitov.com/2019/06/23/101-quick-sort-in-perl-6/
    return @data if @data.elems <= 1;

    my ($pivot,@left, @right) = @data[0];

    for @data[1..*] -> $x { $x < $pivot ?? push @left, $x !! push @right, $x }

    return flat(quick-sort(@left), $pivot, quick-sort(@right));
}

sub comparesorts($rounds, @tosort) {
   my ( $iavg, $mavg, $qavg, $t );

   for (<i m q> xx $rounds).flat.pick(*) -> \sort_type {
      given sort_type {
         when 'i' { $t = now ; insertion_sort @tosort ; $iavg += now - $t } 
         when 'm' { $t = now ; merge_sort     @tosort ; $mavg += now - $t } 
	 when 'q' { $t = now ; quick-sort     @tosort ; $qavg += now - $t }
      }
   }
   return $iavg, $mavg, $qavg  »/»  $rounds
}

for <ones presorted randomized>Z(@allones,@sequential,@randomized) -> ($t,@d) {
   say "Average sort times for $size $t:";
   { say "\tinsertion sort\t$_[0]\n\tmerge sort\t$_[1]\n\tquick sort\t$_[2]" }(comparesorts $rounds,@d)
}</syntaxhighlight>
{{out}}
<pre>Average sort times for 2000 ones:
        insertion sort  0.112333083
        merge sort      0.506624066
        quick sort      5.899009606666667
Average sort times for 2000 presorted:
        insertion sort  0.03596163
        merge sort      0.474839352
        quick sort      5.896118350666666
Average sort times for 2000 randomized:
        insertion sort  5.352926729
        merge sort      0.784896982
        quick sort      0.11422247299999999</pre>

=={{header|REXX}}==
One goal for this REXX program was to include as many different sorts (that sorted arrays and not lists).

Because of the disparencies of some sorting algorithms, &nbsp; the range of numbers was chosen to be &nbsp; '''5''' &nbsp; so that the 
<br>slower sorts wouldn't consume a lot of time trying to sort larger arrays. 

The number of ranges can be increased at the expense of a wider display of output. 
<syntaxhighlight lang="rexx">/*REXX pgm compares various sorts for 3 types of input sequences: ones/ascending/random.*/
parse arg ranges start# seed .                   /*obtain optional arguments from the CL*/
if ranges=='' | ranges==","  then ranges=     5  /*Not Specified?  Then use the default.*/
if start#=='' | start#==","  then start#=   250  /* "      "         "   "   "     "    */
if   seed=='' |   seed==","  then   seed=  1946  /*use a repeatable seed for RANDOM  BIF*/
if datatype(seed, 'W')  then call random ,,seed  /*Specified?  Then use as a RANDOM seed*/
kinds= 3;      hdr=;       #= start#             /*hardcoded/fixed number of datum kinds*/
   do ra=1  for ranges
   hdr= hdr || center( commas(#) "numbers", 25)'│'  /*(top) header for the output title.*/
     do ki=1  for kinds
     call gen@@ #, ki
     call set@;  call time 'R';  call bubble     #;     bubble.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call cocktail   #;   cocktail.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call cocktailSB #; cocktailSB.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call comb       #;       comb.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call exchange   #;   exchange.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call gnome      #;      gnome.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call heap       #;       heap.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call insertion  #;  insertion.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call merge      #;      merge.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call pancake    #;    pancake.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call quick      #;      quick.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call radix      #;      radix.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call selection  #;  selection.ra.ki= format(time("E"),,2)
     call set@;  call time 'R';  call shell      #;      shell.ra.ki= format(time("E"),,2)
     end   /*ki*/
   #= # + #                                                         /*double # elements.*/
   end     /*ra*/
say;                             say;    say                        /*say blank sep line*/
say center('         ', 11     ) "│"left(hdr, length(hdr)-1)"│"     /*replace last char.*/
                            reps= ' allONES  ascend  random │'      /*build a title bar.*/
xreps=       copies( center(reps, length(reps)), ranges)            /*replicate ranges. */
creps= left(xreps, length(xreps)-1)"│"                              /*replace last char.*/
say center('sort type', 11     ) "│"creps;                       Lr= length(reps)
                                        xcreps= copies( left('', Lr-1, '─')"┼", ranges)
say center(''         , 12, '─')"┼"left(xcreps, length(xcreps)-1)"┤"
call show 'bubble'                               /* ◄──── show results for bubble  sort.*/
call show 'cocktail'                             /* ◄────   "     "     "  cocktail   " */
call show 'cocktailSB'    /*+Shifting Bounds*/   /* ◄────   "     "     "  cocktailSB " */
call show 'comb'                                 /* ◄────   "     "     "  comb       " */
call show 'exchange'                             /* ◄────   "     "     "  exchange   " */
call show 'gnome'                                /* ◄────   "     "     "  gnome      " */
call show 'heap'                                 /* ◄────   "     "     "  heap       " */
call show 'insertion'                            /* ◄────   "     "     "  insertion  " */
call show 'merge'                                /* ◄────   "     "     "  merge      " */
call show 'pancake'                              /* ◄────   "     "     "  pancake    " */
call show 'quick'                                /* ◄────   "     "     "  quick      " */
call show 'radix'                                /* ◄────   "     "     "  radix      " */
call show 'selection'                            /* ◄────   "     "     "  shell      " */
call show 'shell'                                /* ◄────   "     "     "  shell      " */
say translate(center(''         , 12, '─')"┴"left(xcreps, length(xcreps)-1)"┘",  '┴', "┼")
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?;  do jc=length(?)-3  to 1  by -3; ?=insert(',', ?, jc); end;  return ?
inOrder: parse arg n; do j=1  for n-1;  k= j+1;  if @.j>@.k  then return 0; end;  return 1
set@:   @.=;          do a=1  for #;                 @.a= @@.a;             end;  return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen@@: procedure expose @@.; parse arg n,kind;  nn= min(n, 100000)     /*1e5≡REXX's max.*/
              do j=1 for nn;      select
                                  when kind==1  then  @@.j= 1               /*all ones. */
                                  when kind==2  then  @@.j= j               /*ascending.*/
                                  when kind==3  then  @@.j= random(, nn)    /*random.   */
                                  end   /*select*/
              end   /*j*/;                                              return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show:  parse arg aa;  _= left(aa, 11)  "│"
                                do   ra=1  for ranges
                                  do ki=1  for kinds
                                  _= _  right( value(aa || . || ra || . || ki),  7, ' ')
                                  end   /*k*/
                                _= _  "│"
                                end     /*r*/;       say _;             return
/*──────────────────────────────────────────────────────────────────────────────────────*/
bubble:   procedure expose @.;  parse arg n         /*N: is the number of  @  elements. */
            do m=n-1  by -1  until ok;         ok=1 /*keep sorting  @  array until done.*/
              do j=1  for m;  k=j+1;  if @.j<=@.k  then iterate    /*elements in order? */
              _=@.j;  @.j=@.k;  @.k=_;         ok=0 /*swap 2 elements; flag as not done.*/
              end   /*j*/
            end     /*m*/;                                              return
/*──────────────────────────────────────────────────────────────────────────────────────*/
cocktail: procedure expose @.;    parse arg N;   nn= N-1     /*N:  is number of items.  */
            do until done;   done= 1
                do j=1   for nn;                jp= j+1
                if @.j>@.jp  then do;  done=0;  _=@.j;  @.j=@.jp;  @.jp=_;  end
                end   /*j*/
            if done  then leave                              /*No swaps done?  Finished.*/
                do k=nn  for nn  by -1;         kp= k+1
                if @.k>@.kp  then do;  done=0;  _=@.k;  @.k=@.kp;  @.kp=_;  end
                end   /*k*/
            end       /*until*/;                                        return
/*──────────────────────────────────────────────────────────────────────────────────────*/
cocktailsb: procedure expose @.;    parse arg N              /*N:  is number of items.  */
                             end$= N - 1;     beg$= 1
            do while beg$ <= end$
            beg$$= end$;               end$$= beg$
                do j=beg$ to end$;                   jp= j + 1
                if @.j>@.jp  then do;  _=@.j;  @.j=@.jp;  @.jp=_;  end$$=j;  end
                end   /*j*/
            end$= end$$ - 1
                do k=end$  to beg$  by -1;           kp= k + 1
                if @.k>@.kp  then do;  _=@.k;  @.k=@.kp;  @.kp=_;  beg$$=k;  end
                end   /*k*/
            beg$= beg$$ + 1
            end       /*while*/;                                        return
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb:  procedure expose @.;   parse arg n        /*N:  is the number of  @  elements.   */
       g= n-1                                    /*G:  is the gap between the sort COMBs*/
             do  until g<=1 & done;    done= 1   /*assume sort is done  (so far).       */
             g= g * 0.8  % 1                     /*equivalent to:   g= trunc( g / 1.25) */
             if g==0  then g= 1                  /*handle case of the gap is too small. */
                do j=1  until $>=n;    $= j + g  /*$:     a temporary index  (pointer). */
                if @.j>@.$  then do;   _= @.j;     @.j= @.$;    @.$= _;    done= 0;    end
                end   /*j*/                      /* [↑]  swap two elements in the array.*/
             end      /*until*/;       return
/*──────────────────────────────────────────────────────────────────────────────────────*/
exchange: procedure expose @.;  parse arg n 1 h  /*both  N  and  H  have the array size.*/
             do while h>1;                      h= h % 2
                do i=1  for n-h;       j= i;    k= h+i
                   do while @.k<@.j
                   _= @.j;  @.j= @.k;  @.k= _;  if h>=j  then leave;  j= j-h;  k= k-h
                   end   /*while @.k<@.j*/
                end      /*i*/
             end         /*while h>1*/;                       return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gnome: procedure expose @.;  parse arg n;      k= 2               /*N: is number items. */
          do j=3  while k<=n;                  p= k - 1           /*P: is previous item.*/
          if @.p<<=@.k  then do;      k= j;    iterate;   end     /*order is OK so far. */
          _= @.p;       @.p= @.k;     @.k= _                      /*swap two @ entries. */
          k= k - 1;     if k==1  then k= j;    else j= j-1        /*test for 1st index. */
          end    /*j*/;                                return
/*──────────────────────────────────────────────────────────────────────────────────────*/
heap:  procedure expose @.; arg n;  do j=n%2  by -1  to 1;   call heapS j,n;  end  /*j*/
             do n=n  by -1  to 2;    _= @.1;    @.1= @.n;    @.n= _;   call heapS 1,n-1
             end   /*n*/;           return       /* [↑]  swap two elements; and shuffle.*/

heapS: procedure expose @.;  parse arg i,n;        $= @.i            /*obtain parent.*/
             do  while i+i<=n;   j= i+i;   k= j+1;    if k<=n  then  if @.k>@.j  then j= k
             if $>=@.j  then leave;      @.i= @.j;    i= j
             end   /*while*/;            @.i= $;      return            /*define lowest.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
insertion:  procedure expose @.;   parse arg n
                   do i=2  to n;   $= @.i;       do j=i-1  by -1  to 1  while @.j>$
                                                 _= j + 1;        @._= @.j
                                                 end   /*j*/
                   _= j + 1;       @._= $
                   end   /*i*/;                                         return
/*──────────────────────────────────────────────────────────────────────────────────────*/
merge: procedure expose @. !.;   parse arg n, L;   if L==''  then do;  !.=;  L= 1;  end
          if n==1  then return;     h= L + 1
          if n==2  then do; if @.L>@.h  then do; _=@.h; @.h=@.L; @.L=_; end; return;  end
          m= n % 2                                     /* [↑]  handle case of two items.*/
          call merge  n-m, L+m                         /*divide items  to the left   ···*/
          call merger m,   L,   1                      /*   "     "     "  "  right  ···*/
          i= 1;                     j= L + m
                     do k=L  while k<j                 /*whilst items on right exist ···*/
                     if j==L+n  |  !.i<=@.j  then do;     @.k= !.i;     i= i + 1;      end
                                             else do;     @.k= @.j;     j= j + 1;      end
                     end   /*k*/;                         return

merger: procedure expose @. !.;  parse arg n,L,T
           if n==1  then do;  !.T= @.L;                                       return;  end
           if n==2  then do;  h= L + 1;   q= T + 1;  !.q= @.L;    !.T= @.h;   return;  end
           m= n % 2                                    /* [↑]  handle case of two items.*/
           call merge  m,   L                          /*divide items  to the left   ···*/
           call merger n-m, L+m, m+T                   /*   "     "     "  "  right  ···*/
           i= L;                     j= m + T
                     do k=T  while k<j                 /*whilst items on left exist  ···*/
                     if j==T+n  |  @.i<=!.j  then do;     !.k= @.i;     i= i + 1;      end
                                             else do;     !.k= !.j;     j= j + 1;      end
                     end   /*k*/;                         return
/*──────────────────────────────────────────────────────────────────────────────────────*/
pancake: procedure expose @.;   parse arg n .;               if inOrder(n)  then return
             do n=n  by -1  for n-1
             != @.1;   ?= 1;                do j=2  to n;    if @.j<=!  then iterate
                                            != @.j;          ?= j
                                            end   /*j*/
             call panFlip ?;   call panFlip n
             end   /*n*/;                                               return

panFlip: parse arg y;  do i=1  for (y+1)%2; yi=y-i+1; _=@.i; @.i=@.yi; @.yi=_; end; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
quick: procedure expose @.; a.1=1; parse arg b.1; $= 1 /*access @.; get #; define pivot.*/
       if inOrder(b.1)  then return
             do  while  $\==0;     L= a.$;    t= b.$;     $= $-1;   if t<2  then iterate
             H= L+t-1;             ?= L+t%2
             if @.H<@.L  then if @.?<@.H  then do;  p=@.H;  @.H=@.L;  end
                                          else if @.?>@.L  then p=@.L
                                                           else do;  p=@.?;  @.?=@.L;  end
                         else if @.?<@.L  then p=@.L
                                          else if @.?>@.H  then do;  p=@.H;  @.H=@.L;  end
                                                           else do;  p=@.?;  @.?=@.L;  end
             j= L+1;                           k=h
                    do forever
                        do j=j         while j<k & @.j<=p;  end     /*a tinie─tiny loop.*/
                        do k=k  by -1  while j<k & @.k>=p;  end     /*another   "    "  */
                    if j>=k  then leave                             /*segment finished? */
                    _= @.j;       @.j= @.k;             @.k= _      /*swap J&K elements.*/
                    end   /*forever*/
             $= $+1;            k= j-1;   @.L= @.k;     @.k= p
             if j<=?  then do;  a.$= j;   b.$= H-j+1;   $= $+1;  a.$= L;  b.$= k-L;    end
                      else do;  a.$= L;   b.$= k-L;     $= $+1;  a.$= j;  b.$= H-j+1;  end
             end          /*while $¬==0*/;              return
/*──────────────────────────────────────────────────────────────────────────────────────*/
radix:   procedure expose @.;  parse arg size,w;   mote= c2d(' ');    #= 1;   !.#._n= size
!.#._b= 1;                     if w==''  then w= 8
!.#._i= 1;  do i=1  for size;  y=@.i;  @.i= right(abs(y), w, 0);  if y<0  then @.i= '-'@.i
            end  /*i*/                                            /* [↑]  negative case.*/

     do  while #\==0;  ctr.= 0;  L= 'ffff'x;   low= !.#._b;   n= !.#._n;   $= !.#._i;   H=
     #= #-1                                                      /* [↑]   is the radix. */
           do j=low  for n;      parse var  @.j  =($)  _  +1;    ctr._= ctr._ + 1
           if ctr._==1 & _\==''  then do;  if _<<L  then L=_;    if _>>H  then H=_
                                      end  /*  ↑↑                                       */
           end   /*j*/                     /*  └┴─────◄───  <<   is a strict comparison.*/
     _=                                    /*      ┌──◄───  >>    " "    "        "     */
     if L>>H  then iterate                 /*◄─────┘                                    */
     if L==H & ctr._==0  then do; #= #+1;  !.#._b= low;  !.#._n= n;  !.#._i= $+1;  iterate
                              end
     L= c2d(L);   H= c2d(H);      ?= ctr._ + low;        top._= ?;          ts= mote
     max= L
                  do k=L  to H;   _= d2c(k, 1);   c= ctr._  /* [↓]  swap 2 item radices.*/
                  if c>ts  then parse value  c k  with  ts max;     ?= ?+c;       top._= ?
                  end   /*k*/
     piv= low                                    /*set PIVot to the low part of the sort*/
             do  while piv<low+n
             it= @.piv
                        do forever;     parse var it  =($)  _  +1;         c= top._ -1
                        if piv>=c  then leave;   top._= c;    ?= @.c;    @.c= it;    it= ?
                        end   /*forever*/
             top._= piv;                         @.piv= it;        piv= piv + ctr._
             end   /*while piv<low+n */
     i= max
          do  until i==max;  _= d2c(i, 1);     i= i+1;     if i>H  then i= L;     d= ctr._
          if d<=mote  then do;         if d<2  then iterate;          b= top._
                             do k=b+1  for d-1;                       q= @.k
                               do j=k-1  by -1  to b  while q<<@.j;  jp= j+1;   @.jp= @.j
                               end   /*j*/
                                                                     jp= j+1;   @.jp= q
                             end     /*k*/
                           iterate
                           end
          #= #+1;       !.#._b= top._;       !.#._n= d;        !.#._i= $ + 1
          end   /*until i==max*/
     end        /*while #\==0 */
#= 0                                             /* [↓↓↓]  handle neg. and pos. arrays. */
        do i=size  by -1  for size;    if @.i>=0  then iterate;     #= #+1;      @@.#= @.i
        end   /*i*/
        do j=1  for size;   if @.j>=0  then do;  #= #+1;   @@.#= @.j;  end;    @.j= @@.j+0
        end   /*j*/                              /* [↑↑↑]  combine 2 lists into 1 list. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
selection: procedure expose @.;  parse arg n
              do j=1  for n-1;         _= @.j;         p= j
                  do k=j+1  to n;      if @.k>=_  then iterate
                  _= @.k;              p= k      /*this item is out─of─order, swap later*/
                  end   /*k*/
              if p==j  then iterate              /*if the same, the order of items is OK*/
              _= @.j;     @.j= @.p;    @.p=      /*swap 2 items that're out─of─sequence.*/
              end       /*j*/;         return
/*──────────────────────────────────────────────────────────────────────────────────────*/
shell: procedure expose @.;   parse arg N        /*obtain the  N  from the argument list*/
       i= N % 2                                  /*%   is integer division in REXX.     */
                  do  while i\==0
                         do j=i+1  to N;    k= j;      p= k-i         /*P: previous item*/
                         _= @.j
                                do  while k>=i+1 & @.p>_;   @.k= @.p;    k= k-i;    p= k-i
                                end   /*while k≥i+1*/
                         @.k= _
                         end          /*j*/
                  if i==2  then i= 1
                           else i= i * 5 % 11
                  end                 /*while i¬==0*/;                  return</syntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}

(Shown at &nbsp; '''<sup>7</sup>/<sub>8</sub>''' &nbsp; size.)
<pre style="font-size:88%">
            │       250 numbers       │       500 numbers       │      1,000 numbers      │      2,000 numbers      │      4,000 numbers      │
 sort type  │ allONES  ascend  random │ allONES  ascend  random │ allONES  ascend  random │ allONES  ascend  random │ allONES  ascend  random │
────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┤
bubble      │    0.00    0.00    0.06 │    0.00    0.00    0.28 │    0.00    0.00    1.11 │    0.00    0.02    4.39 │    0.00    0.00   17.53 │
cocktail    │    0.00    0.00    0.08 │    0.00    0.02    0.27 │    0.00    0.02    1.13 │    0.00    0.00    4.75 │    0.00    0.00   18.19 │
cocktailSB  │    0.00    0.00    0.05 │    0.02    0.00    0.22 │    0.00    0.00    0.91 │    0.02    0.00    3.59 │    0.02    0.02   14.16 │
comb        │    0.02    0.00    0.02 │    0.00    0.00    0.02 │    0.03    0.03    0.03 │    0.06    0.06    0.08 │    0.14    0.14    0.20 │
exchange    │    0.00    0.00    0.00 │    0.02    0.02    0.02 │    0.02    0.00    0.05 │    0.03    0.02    0.08 │    0.06    0.05    0.20 │
gnome       │    0.00    0.06    0.06 │    0.00    0.11    0.24 │    0.00    0.16    0.86 │    0.00    3.50    3.61 │    0.02    8.95   14.08 │
heap        │    0.00    0.00    0.00 │    0.02    0.02    0.02 │    0.03    0.06    0.05 │    0.05    0.11    0.11 │    0.08    0.25    0.25 │
insertion   │    0.00    0.00    0.03 │    0.00    0.02    0.13 │    0.00    0.00    0.47 │    0.02    0.02    1.88 │    0.02    0.02    7.84 │
merge       │    0.02    0.02    0.02 │    0.00    0.00    0.02 │    0.03    0.03    0.03 │    0.05    0.05    0.08 │    0.11    0.13    0.17 │
pancake     │    0.00    0.00    0.08 │    0.02    0.00    0.30 │    0.00    0.00    1.20 │    0.02    0.02    4.73 │    0.02    0.00   19.63 │
quick       │    0.00    0.00    0.00 │    0.00    0.00    0.00 │    0.00    0.00    0.02 │    0.00    0.00    0.05 │    0.00    0.00    0.09 │
radix       │    0.00    0.00    0.00 │    0.00    0.03    0.03 │    0.02    0.03    0.05 │    0.05    0.08    0.08 │    0.09    0.14    0.14 │
selection   │    0.02    0.03    0.03 │    0.09    0.08    0.08 │    0.33    0.33    0.38 │    1.22    1.39    1.55 │    4.95    4.86    5.30 │
shell       │    0.02    0.00    0.00 │    0.00    0.00    0.02 │    0.02    0.02    0.05 │    0.05    0.05    0.09 │    0.13    0.11    0.22 │
────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┘
</pre>

=={{header|Ruby}}==
<syntaxhighlight lang="ruby">class Array
  def radix_sort(base=10)       # negative value is inapplicable.
    ary = dup
    rounds = (Math.log(ary.max)/Math.log(base)).ceil
    rounds.times do |i|
      buckets = Array.new(base){[]}
      base_i = base**i
      ary.each do |n|
        digit = (n/base_i) % base
        buckets[digit] << n
      end
      ary = buckets.flatten
    end
    ary
  end
  
  def quick_sort
    return self  if size <= 1
    pivot = sample
    g = group_by{|x| x<=>pivot}
    g.default = []
    g[-1].quick_sort + g[0] + g[1].quick_sort
  end
  
  def shell_sort
    inc = size / 2
    while inc > 0
      (inc...size).each do |i|
        value = self[i]
        while i >= inc and self[i - inc] > value
          self[i] = self[i - inc]
          i -= inc
        end
        self[i] = value
      end
      inc = (inc == 2 ? 1 : (inc * 5.0 / 11).to_i)
    end
    self
  end
  
  def insertion_sort
    (1...size).each do |i|
      value = self[i]
      j = i - 1
      while j >= 0 and self[j] > value
        self[j+1] = self[j]
        j -= 1
      end
      self[j+1] = value
    end
    self
  end
  
  def bubble_sort
    (1...size).each do |i|
      (0...size-i).each do |j|
        self[j], self[j+1] = self[j+1], self[j]  if self[j] > self[j+1]
      end
    end
    self
  end
end

data_size = [1000, 10000, 100000, 1000000]
data = []
data_size.each do |size|
  ary = *1..size
  data << [ [1]*size, ary, ary.shuffle, ary.reverse ]
end
data = data.transpose

data_type = ["set to all ones", "ascending sequence", "randomly shuffled", "descending sequence"]
print "Array size:          "
puts data_size.map{|size| "%9d" % size}.join

data.each_with_index do |arys,i|
  puts "\nData #{data_type[i]}:"
  [:sort, :radix_sort, :quick_sort, :shell_sort, :insertion_sort, :bubble_sort].each do |m|
    printf "%20s ", m
    flag = true
    arys.each do |ary|
      if flag
        t0 = Time.now
        ary.dup.send(m)
        printf "  %7.3f", (t1 = Time.now - t0)
        flag = false  if t1 > 2
      else
        print "   --.---"
      end
    end
    puts
  end
end</syntaxhighlight>
Array#sort is a built-in method.

{{out}}
<pre>
Array size:               1000    10000   100000  1000000

Data set to all ones:
                sort     0.000    0.001    0.005    0.043
          radix_sort     0.000    0.002    0.012    0.084
          quick_sort     0.000    0.002    0.020    0.197
          shell_sort     0.002    0.018    0.234    2.897
      insertion_sort     0.000    0.002    0.020    0.198
         bubble_sort     0.064    6.328   --.---   --.---

Data ascending sequence:
                sort     0.000    0.000    0.002    0.020
          radix_sort     0.001    0.010    0.128    1.546
          quick_sort     0.004    0.058    0.521    5.996
          shell_sort     0.001    0.019    0.234    2.882
      insertion_sort     0.000    0.002    0.021    0.195
         bubble_sort     0.065    6.453   --.---   --.---

Data randomly shuffled:
                sort     0.000    0.002    0.024    0.263
          radix_sort     0.001    0.011    0.126    1.529
          quick_sort     0.004    0.081    0.522    6.192
          shell_sort     0.003    0.033    0.498    5.380
      insertion_sort     0.027    2.627   --.---   --.---
         bubble_sort     0.122   11.779   --.---   --.---

Data descending sequence:
                sort     0.000    0.001    0.001    0.021
          radix_sort     0.001    0.012    0.125    1.560
          quick_sort     0.004    0.061    0.522    5.873
          shell_sort     0.003    0.028    0.316    3.829
      insertion_sort     0.053    5.298   --.---   --.---
         bubble_sort     0.206   17.232   --.---   --.---
</pre>

=={{header|Tcl}}==
===Background===
The <code>lsort</code> command is Tcl's built-in sorting engine. It is implemented in C as a mergesort, so while it is theoretically slower than quicksort, it is a stable sorting algorithm too, which produces results that tend to be less surprising in practice. This task will be matching it against multiple manually-implemented sorting procedures.

===Observations===
Obviously, the built-in compiled sort command will be much faster than any Tcl-coded implementation. The Tcl-coded [[Merge sort#Tcl|mergesort]] is up to 3 orders of magnitude slower.

The [[Shell sort#Tcl|shellsort]] implementation suffers, relative to other algorithms, in the case where the list is already sorted.

===Code===
{{libheader|Tk}}
{{tcllib|struct::list}}
<syntaxhighlight lang="tcl">###############################################################################
# measure and plot times
package require Tk
package require struct::list
namespace path ::tcl::mathfunc

proc create_log10_plot {title xlabel ylabel xs ys labels shapes colours} {
    set w [toplevel .[clock clicks]]
    wm title $w $title
    pack [canvas $w.c -background white]
    pack [canvas $w.legend -background white]
    update
    plot_log10 $w.c $w.legend $title $xlabel $ylabel $xs $ys $labels $shapes $colours
    $w.c config -scrollregion [$w.c bbox all]
    update
}

proc plot_log10 {canvas legend title xlabel ylabel xs ys labels shapes colours} {
    global xfac yfac
    set log10_xs [map {_ {log10 $_}} $xs]
    foreach series $ys {
        lappend log10_ys [map {_ {log10 $_}} $series]
    }
    set maxx [max {*}$log10_xs]
    set yvalues [lsort -real [struct::list flatten $log10_ys]]
    set firstInf [lsearch $yvalues Inf]
    set maxy [lindex $yvalues [expr {$firstInf == -1 ? [llength $yvalues] - 1 : $firstInf - 1}]]

    set xfac [expr {[winfo width $canvas] * 0.8/$maxx}]
    set yfac [expr {[winfo height $canvas] * 0.8/$maxy}]

    scale $canvas x 0 $maxx $xfac "log10($xlabel)"
    scale $canvas y 0 $maxy $yfac "log10($ylabel)" $maxx $xfac

    $legend create text 30 0 -text $title -anchor nw
    set count 1
    foreach series $log10_ys shape $shapes colour $colours label $labels {
        plotxy $canvas $log10_xs $series $shape $colour
        legenditem $legend [incr count] $shape $colour $label
    }
}

proc map {lambda list} {
    set res [list]
    foreach item $list {lappend res [apply $lambda $item]}
    return $res
}

proc legenditem {legend pos shape colour label} {
    set y [expr {$pos * 15}]
    $shape $legend 20 $y -fill $colour
    $legend create text 30 $y -text $label -anchor w
}

# The actual plotting engine
proc plotxy {canvas _xs _ys shape colour} {
    global xfac yfac
    foreach x $_xs y $_ys {
        if {$y < Inf} {
            lappend xs $x
            lappend ys $y
        }
    }
    set coords [list]
    foreach x $xs y $ys {
        set coord_x [expr {$x*$xfac}]
        set coord_y [expr {-$y*$yfac}]
        $shape $canvas $coord_x $coord_y -fill $colour
        lappend coords $coord_x $coord_y
    }
    $canvas create line $coords -smooth true
}
# Rescales the contents of the given canvas
proc scale {canvas direction from to fac label {other_to 0} {other_fac 0}} {
    set f [expr {$from*$fac}]
    set t [expr {$to*$fac}]
    switch -- $direction {
        x {
            set f [expr {$from * $fac}]
            set t [expr {$to * $fac}]
            # create x-axis
            $canvas create line $f 0 $t 0
            $canvas create text $f 0 -anchor nw -text $from
            $canvas create text $t 0 -anchor n -text [format "%.1f" $to]
            $canvas create text [expr {($f+$t)/2}] 0 -anchor n -text $label

        }
        y {
            set f [expr {$from * -$fac}]
            set t [expr {$to * -$fac}]
            # create y-axis
            $canvas create line 0 $f 0 $t
            $canvas create text 0 $f -anchor se -text $from
            $canvas create text 0 $t -anchor e -text [format "%.1f" $to]
            $canvas create text 0 [expr {($f+$t)/2}] -anchor e -text $label
            # create gridlines
            set xmax [expr {$other_to * $other_fac}]
            for {set i 1} {$i < $to} {incr i} {
                set y [expr {$i * -$fac}]
                $canvas create line 0 $y $xmax $y -dash .
            }
        }
    }
}
# Helper to make points, which are otherwise not a native item type
proc dot {canvas x y args} {
    set id [$canvas create oval [expr {$x-3}] [expr {$y-3}] \
                [expr {$x+3}] [expr {$y+3}]]
    $canvas itemconfigure $id {*}$args
}
proc square {canvas x y args} {
    set id [$canvas create rectangle [expr {$x-3}] [expr {$y-3}] \
                [expr {$x+3}] [expr {$y+3}]]
    $canvas itemconfigure $id {*}$args
}
proc cross {canvas x y args} {
    set l1 [$canvas create line [expr {$x-3}] $y [expr {$x+3}] $y]
    set l2 [$canvas create line $x [expr {$y-3}] $x [expr {$y+3}]]
    $canvas itemconfigure $l1 {*}$args
    $canvas itemconfigure $l2 {*}$args
}
proc x {canvas x y args} {
    set l1 [$canvas create line [expr {$x-3}] [expr {$y-3}] [expr {$x+3}] [expr {$y+3}]]
    set l2 [$canvas create line [expr {$x+3}] [expr {$y-3}] [expr {$x-3}] [expr {$y+3}]]
    $canvas itemconfigure $l1 {*}$args
    $canvas itemconfigure $l2 {*}$args
}
proc triangleup {canvas x y args} {
    set id [$canvas create polygon $x [expr {$y-4}] \
                [expr {$x+4}] [expr {$y+4}] \
                [expr {$x-4}] [expr {$y+4}]]
    $canvas itemconfigure $id {*}$args
}
proc triangledown {canvas x y args} {
    set id [$canvas create polygon $x [expr {$y+4}] \
                [expr {$x+4}] [expr {$y-4}] \
                [expr {$x-4}] [expr {$y-4}]]
    $canvas itemconfigure $id {*}$args
}

wm withdraw .

#####################################################################
# list creation procedures
proc ones n {
    lrepeat $n 1
}
proc reversed n {
    while {[incr n -1] >= 0} {
        lappend result $n
    }
    return $result
}  
proc random n {
    for {set i 0} {$i < $n} {incr i} {
        lappend result [expr {int($n * rand())}]
    }
    return $result
}

set algorithms {lsort quicksort shellsort insertionsort bubblesort mergesort}
set sizes {1 10 100 1000 10000 100000}
set types {ones reversed random} 
set shapes {dot square cross triangleup triangledown x}
set colours {red blue black brown yellow black}

# create some lists to be used by all sorting algorithms
array set lists {}
foreach size $sizes {
    foreach type $types {
        set lists($type,$size) [$type $size]
    }
}

set runs 10

# header
fconfigure stdout -buffering none
puts -nonewline [format "%-16s" "list length:"]
foreach size $sizes {
    puts -nonewline [format " %10d" $size]
}
puts ""

# perform the sort timings and output results
foreach type $types {
    puts "\nlist type: $type"
    set times [list]
    foreach algo $algorithms {
        set errs [list]
        set thesetimes [list]
        $algo {} ;# call it once to ensure it's compiled
        
        puts -nonewline [format "   %-13s" $algo]
        foreach size $sizes {
            # some implementations are just too slow
            if {$type ne "ones" && (
                ($algo eq "insertionsort" && $size > 10000) ||
                ($algo eq "bubblesort" && $size > 1000))
            } {
                set time Inf
            } else {
                # OK, do it
                if {[catch {time [list $algo $lists($type,$size)] $runs} result] != 0} {
                    set time Inf
                    lappend errs $result
                } else {
                    set time [lindex [split $result] 0]
                }
            }
            lappend thesetimes $time
            puts -nonewline [format " %10s" $time]
        }
        puts ""
        if {[llength $errs] > 0} {
            puts [format "      %s" [join $errs "\n      "]]
        }
        lappend times $thesetimes
    }
    create_log10_plot "Sorting a '$type' list" size time $sizes $times $algorithms $shapes $colours
}
puts "\ntimes in microseconds, average of $runs runs"</syntaxhighlight>

{{omit from|GUISS}}

===Output===
<pre>list length:              1         10        100       1000      10000     100000

list type: ones
   lsort                0.8        1.2        7.2       71.9     1042.7    11428.9
   quicksort            1.1        9.0       40.6      369.5     3696.4    37478.4
   shellsort            1.4       26.0      249.1     4003.4    56278.7   717790.6
   insertionsort        1.1        6.4       59.0      528.1     5338.9    54913.0
   bubblesort           1.9        5.1       31.9      308.8     3259.1    31991.2
   mergesort            1.3       61.1      704.2     9275.4   224784.4 14599414.6

list type: reversed
   lsort                1.0        1.6        9.9      112.1     1434.9    20181.0
   quicksort            1.5       55.3      495.6     6705.9    79984.0   963975.0
   shellsort            1.5       25.9      457.0     7118.6    92497.5  1210143.9
   insertionsort        1.2       21.0     1645.0   159262.2 15859610.8        Inf
   bubblesort           1.9      445.0    46526.6  4665550.4        Inf        Inf
   mergesort            1.4       61.7      842.8     9572.1   215536.6 16938651.0

list type: random
   lsort                1.0        1.7       15.7      300.9     3275.0    58779.5
   quicksort            1.2       28.0      429.1     5609.5    71743.3   923630.4
   shellsort            1.6       26.7      571.0     9031.1   140526.9  2244152.7
   insertionsort        1.3       15.4      832.6    79018.0  7893722.6        Inf
   bubblesort           1.8      256.2    23753.1  2422926.0        Inf        Inf
   mergesort            1.9       60.2      883.5    12505.6   399672.6 49225509.8

times in microseconds, average of 10 runs</pre>
[[Image:Tcl_sort_ones.png]]
[[Image:Tcl_sort_reversed.png]]
[[Image:Tcl_sort_random.png]]

=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
The quick, insertion and shell sorts all use the 'in place' implementations in the Wren-sort module. 

The radix sort is lifted from the task of that name and, although more complicated, appears to be much faster than the Kotlin version.

For the bubble sort, I have used the optimized Kotlin implementation.

I've limited the size of the arrays to 50,000 though even then the program takes the best part of half an hour to run, due to the extreme slowness of the bubble and insertion sorts for large amounts of shuffled data.

Results presented in tabular form as Wren doesn't have a plotting library available at the present time.
<syntaxhighlight lang="ecmascript">import "random" for Random
import "/sort" for Sort
import "/fmt" for Fmt

var rand = Random.new()

var onesSeq = Fn.new { |n| List.filled(n, 1) }

var shuffledSeq = Fn.new { |n|
    var seq = List.filled(n, 0)
    for (i in 0...n) seq[i] = 1 + rand.int(10 * n)
    return seq
}

var ascendingSeq = Fn.new { |n|
    var seq = shuffledSeq.call(n)
    seq.sort()
    return seq
}

var bubbleSort = Fn.new { |a|
    var n = a.count
    while (true) {
        var n2 = 0
        for (i in 1...n) {
            if (a[i - 1] > a[i]) {
                a.swap(i, i - 1)
                n2 = i
            }
        }
        n = n2
        if (n == 0) break
    }
}

// counting sort of 'a' according to the digit represented by 'exp'
var countSort = Fn.new { |a, exp|
    var n = a.count
    var output = [0] * n
    var count  = [0] * 10
    for (i in 0...n) {
        var t = (a[i]/exp).truncate % 10
        count[t] = count[t] + 1
    }
    for (i in 1..9) count[i] = count[i] + count[i-1]
    for (i in n-1..0) {
        var t = (a[i]/exp).truncate % 10
        output[count[t] - 1] = a[i]
        count[t] = count[t] - 1
    }
    for (i in 0...n) a[i] = output[i]
}

// sorts 'a' in place
var radixSort = Fn.new { |a|
    // check for negative elements
    var min = a.reduce { |m, i| (i < m) ? i : m }
    // if there are any, increase all elements by -min
    if (min < 0) (0...a.count).each { |i| a[i] = a[i] - min }
    // now get the maximum to know number of digits
    var max = a.reduce { |m, i| (i > m) ? i : m }
    // do counting sort for each digit
    var exp = 1
    while ((max/exp).truncate > 0) {
        countSort.call(a, exp)
        exp = exp * 10
    }
    // if there were negative elements, reduce all elements by -min
    if (min < 0) (0...a.count).each { |i| a[i] = a[i] + min }
}

var measureTime = Fn.new { |sort, seq|
    var start = System.clock
    sort.call(seq)
    return ((System.clock - start) * 1e6).round // microseconds
}

var runs = 10
var lengths = [1, 10, 100, 1000, 10000, 50000]
var sorts = [
    bubbleSort,
    Fn.new { |a| Sort.insertion(a) },
    Fn.new { |a| Sort.quick(a) },
    radixSort,
    Fn.new { |a| Sort.shell(a) }
]

var sortTitles = ["Bubble", "Insert", "Quick ", "Radix ", "Shell "]
var seqTitles  = ["All Ones", "Ascending", "Shuffled"]
var totals = List.filled(seqTitles.count, null)
for (i in 0...totals.count) {
    totals[i] = List.filled(sorts.count, null)
    for (j in 0...sorts.count) totals[i][j] = List.filled(lengths.count, 0)
}
var k = 0
for (n in lengths) {
    var seqs = [onesSeq.call(n), ascendingSeq.call(n), shuffledSeq.call(n)]
    for (r in 0...runs) {
        for (i in 0...seqs.count) {
            for (j in 0...sorts.count) {
                var seq = seqs[i].toList
                totals[i][j][k] = totals[i][j][k] + measureTime.call(sorts[j], seq)
            }
        }
    }
    k = k + 1
}
System.print("All timings in microseconds\n")
System.write("Sequence length")
for (len in lengths) Fmt.write("$8d   ", len)
System.print("\n")
for (i in 0...seqTitles.count) {
    System.print("  %(seqTitles[i]):")
    for (j in 0...sorts.count) {
        System.write("    %(sortTitles[j])     ")
        for (k in 0...lengths.count) {
            var time = (totals[i][j][k] / runs).round
            Fmt.write("$8d   ", time)
        }
        System.print()
    }
    System.print("\n")
}</syntaxhighlight>

{{out}}
<pre>
All timings in microseconds

Sequence length       1         10        100       1000      10000      50000   

  All Ones:
    Bubble            1          2          9         61        643       3225   
    Insert            1          3         16        118       1256       6338   
    Quick             1          8         92        983      14746      87660   
    Radix             6         13         62        460       4823      24379   
    Shell             1          5         59        770       9542      48873   


  Ascending:
    Bubble            1          2          8         61        637       3221   
    Insert            1          3         16        118       1251       6371   
    Quick             1          7         65        643       9149      54199   
    Radix             7         23        169       1648      21428     130609   
    Shell             1          5         60        779       9537      49041   


  Shuffled:
    Bubble            1          7        451      37271    4025966   99834073   
    Insert            0          7        295      24040    2597162   64875212   
    Quick             1          8        101       1149      16256      95590   
    Radix             5         24        163       1688      22443     136228   
    Shell             1          8        111       1514      25180     230897   
</pre>

The results are much the same as one might have expected beforehand.

As far as the shuffled data is concerned, quick sort is the fastest though radix and shell sorts are also reasonable performers. Bubble and insertion sorts are very slow indeed for large amounts of data.

Conversely, if the data is already sorted into ascending order, bubble and insertion sorts are much faster than the others and radix sort is the slowest.

If all data is the same, a similar pattern emerges except that radix sort performs better than both shell and quick sorts, the latter being the slowest.