Example Case: Quicksort

Understanding the example case

Quicksort is a fast sorting algorithm, especially in imperative languages where in-place sorting can be done to save on memory. It’s also a frequently used algorithms when demonstrating list comprehensions. The official Erlang documentation gives an example that looks like this:

sort([]) -> []; 
sort([Pivot|T]) ->
    sort([ X || X <- T, X < Pivot]) 
    ++ [Pivot] ++
    sort([ X || X <- T, X >= Pivot]).

It’s a straightforward implementation that works rather well, but there’s a reason why the Erlang standard library uses a mergesort implementation instead. Quicksort has notoriously bad behavior when bad pivots or repeated elements are present. It starts to use quadratically more time on every sorted element. Mergesort, by comparison, doesn’t suffer from that behavior.

We’ll devise an experiment to see whether the quicksort implementation proposed by Erlang is safe or not, to see how applying targeted properties can find fascinating stuff in our ...