Stupid-sort is probably the simplest known deterministic sorting algorithm. It is used for rearranging values in an array to ascending (or descending) order. Its instructional value lies in pointing out how an intuitive, simple algorithm can have a catastrophically low performance in terms of execution time and memory usage. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

According to the Jargon file, stupid-sort is a synonym for bogo-sort. The Jargon File is a glossary of hacker slang. ... According to the Jargon File, bogosort is the archetypal perversely awful algorithm, one example of which is attempting to sort a deck of cards by repeatedly throwing the deck in the air, picking the cards up at random, and then testing whether the cards are in sorted order. ...

Stupid-sort never fails to arrange the data and in the best case (data already in order) it has linear execution time (i.e., its best case execution time is Ω(n), where n is the number of elements in the array). Additionally, the non-recursive form arranges the data in-place, meaning that no extra memory for temporarily storing the data needs to be allocated.

Unlike bubble sort, this sort algorithm starts all over again if there is a wrong order at all. While this simplifies the algorithm a bit, this also leads to a poor runtime performance. Bubble sort, also known as exchange sort, is a simple sorting algorithm. ...

The small code size and memory footprint of the non-recursive stupid-sort actually makes it quite usable in systems with limited code and data space, for example microcontroller systems.

Stupid-sort is a stable sorting algorithm meaning that two values having the same value always stay in the same order. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

The iterative stupid-sort algorithm

The iterative (i.e. non-recursive) Stupid-sort can be described as:

1. Starting from start of the array, scan until two succeeding items that are in wrong order are found.
2. Swap those items and restart the algorithm (go to line 1).
3. The algorithm ends when the end of the array is reached.

 function stupidSort(array) { i := 1 while i < length(array) if array[i + 1] < array[i] then { swap(array[i], array[i + 1]) i:=1 } else i:=i+1 } 

Execution time

Stupid-sort has a best case execution time of O(n), which occurs when the array's elements are already in correct order. The worst-case execution time occurs when the elements are in reverse order. In this case, the algorithm will perform (n³ − n) / 6 + (n − 1) comparisons, resulting in O(n³) performance. For example, the iterative stupid-sort would require 178,957,823 comparisons to sort an array of 1024 items whose elements were initially in reverse order.

...

The recursive stupid-sort algorithm

With recursion, stupid-sort can be made even more stupid than the iterative (non-recursive) form. Recursive stupid-sort can be expressed as:

 function stupidSort(array) { for i from 1 to length(array) - 1 if array[i + 1] < array[i] then { swap(array[i], array[i + 1]) stupidSort(array) } } 

Execution time

The execution time of the recursive form is still Ω(n) .. O(n³) but the recursion calls add overhead so the recursive form is slower than the iterative form. Additionally, the algorithm does not end until every recursion level has traversed the entire array, even if the array is sorted, thus needlessly adding to the number of comparisons performed.

Memory usage

The iterative stupid-sort is not stupid in terms of memory usage since it sorts the array in-place.

Because the recursion occurs inside the for loop and is not tail recursion, it cannot be optimized away by the compiler. In the worst case of elements initially in reverse order, (n² + n) / 2 exchanges must be made during the sorting process. Since every exchange is followed by a recursive call, the memory usage of the recursion stack is O(n²), which can easily lead to stack overflow problems even with today's computers. In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ...

However, relying on each recursion to sort the array allows it to be easily turned into tail recursion. Just return or exit the function immediately after the recursive call. If the tail recursion is optimized, this is then identical to the iterative version. (The only variable used in either version, besides the array parameter, is the index. And the iterative version just sets it to 1, which is exactly the only thing done by the recursive version before entering the loop again.)

Variants

It is simple to produce an O(n²) sort from stupid sort by avoiding starting from the beginning after each swap, instead starting from directly before the swapped elements, knowing that the preceding elements are all still in order. The resulting sort is a simple sort with no nested loops called gnome sort. Gnome sort is a sort algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. ...

Example source codes

Pascal source code for iterative stupid-sort

Stupid

 procedure stupidsort (var a: array of integer); var i: integer; begin i := 0; repeat inc (i); if (a[i+1] < a[i]) then begin exchange (a[i], a[i+1]); i:=0; end; until i = length(A) - 2; end; 

The "exchange" function needed by the algorithm might be:

 procedure exchange (var i, j: integer); var temp: integer; begin temp := i; i := j; j := temp; end; 

Example run of the iterative algorithm

The following printout shows the sorting of an array with 6 items that are in reverse order. Each line is printed when an exchange operation occurs. The hash mark (#) shows which items are swapped. The number of steps shows how many times the algorithm has restarted.

 6 5 4 3 2 1 initial order 6#5 4 3 2 1 (1 step) 5 6#4 3 2 1 (3 steps) 5#4 6 3 2 1 (4 steps) 4 5 6#3 2 1 (7 steps) 4 5#3 6 2 1 (9 steps) 4#3 5 6 2 1 (10 steps) 3 4 5 6#2 1 (14 steps) 3 4 5#2 6 1 (17 steps) 3 4#2 5 6 1 (19 steps) 3#2 4 5 6 1 (20 steps) 2 3 4 5 6#1 (25 steps) 2 3 4 5#1 6 (29 steps) 2 3 4#1 5 6 (32 steps) 2 3#1 4 5 6 (34 steps) 2#1 3 4 5 6 (35 steps) 1 2 3 4 5 6 final order, total 40 steps. 

Python source code for the iterative stupid-sort (in-place)

This version is in-place, so it won't work for immutable types (such as tuples).

 def stupid_sort(a): i = 0 while i < len(a) - 1: if a[i] > a[i + 1]: a[i], a[i + 1] = a[i + 1], a[i] i = 0 continue i += 1 

Python source code for the iterative stupid-sort (not in-place)

This version is not in-place, so it works for immutable types (such as tuples).

 def ssort(iterable): """A simple iterative stupid-sort implementation in python""" seq = list(iterable) seqLen = len(seq) if seqLen <= 1: return seq sorted = False while not sorted: for index in range(seqLen): try: if seq[index] > seq[index+1]: seq[index], seq[index+1] = seq[index+1], seq[index] break except IndexError: sorted = True break return seq 

Pascal source code for the recursive stupid-sort

 procedure stupidsort (var a:array of integer); var i:integer; begin for i:=1 to length(A)-1 do begin if a[i+1]<a[i] then begin exchange (a[i+1],a[i]); stupidsort(a); end; end; end; 

C source code for the iterative stupid-sort

 void stupidSort(int *array, int length) { int temp,i=0; while(i < (length-1) ){ if(array[i+1] < array[i]){ temp=array[i]; array[i]=array[i+1]; array[i+1]=temp; i=0; }else i++; } } 

C source code for the recursive stupid-sort

 void stupidSort(int *array, int length) { int temp,i; for(i=0;i < (length-1);i++){ if(array[i+1] < array[i]){ temp=array[i]; array[i]=array[i+1]; array[i+1]=temp; stupidSort(array,length); } } }