The simplest sorting algorithm

Not all of us have enjoyed a formal computer science education so let's define what a sorting algorithm actually does:

A sorting algorithm takes an array and puts it elements in a certain order. What order means depends on the values stored in the array, e.g. in numerical order for numbers or lexicographic order for strings. ¹

Let's see an example, for an array a = [4,2,3,1], a sorting algorithm applied to a will result in [1,2,3,4] when numerically sorted in ascending order.

Ok, now that we've defined what sorting means let's head over to why I am writing this article. I discovered a paper called Is this the simplest (and most surprising) sorting algorithm ever? on lobste.rs today. Sorting algorithms are often used in basic computer science lectures to teach algorithms. The first algorithm students encounter is very often Bubble sort.

Bubble sort is by no means a complicated algorithm as you can see in the prototypical Go implementation below:

xs := []int{4, 2, 6, 10, 3, -1}

for {
    swapped := false
    for i := 1; i < len(xs); i++ {
        if xs[i-1] > xs[i] {
            xs[i-1], xs[i] = xs[i], xs[i-1]
            swapped = true
        }
    }
    if !swapped {
        break
    }
}
fmt.Println(xs) // prints [-1 2 3 4 6 10]

You can play with the implementation in the Go playground. It just iterates over the array until there is no element to swap anymore. The only complicated thing is to keep around the state if two elements got swapped.

To my surprise the paper mentioned above is describing an even more straightforward way to sort an array:

xs := []int{4, 2, 6, 10, 3, -1}
for i := 0; i < len(xs); i++ {
  for j := 0; j < len(xs); j++ {
    if xs[i] < xs[j] {
      xs[i], xs[j] = xs[j], xs[i]
    }
  }
}
fmt.Println(xs) // prints [-1 2 3 4 6 10]

It does not get much simpler than this and I assume that this might be the first algorithm future computer science students will encounter in their basic lessons. For me this algorithm is easier to remember than the classic bubble sort but the paper states that it is not a good candidate for an algorithm introduction.

You certainly do not want to use it as a first example to introduce students to sorting algorithms. It is not stable, does not work well for external sorting, cannot sort inputs arriving online, and does not benefit from partially sorted inputs.

You can try this one out in the Go playground as well.