The crux of the preceding code lies in the following line:
qsort ys ++ [x] ++ qsort zs
In the preceding statement, notice the following:
- We choose the first element of the list, x as the pivot.
- The list is then split into two parts ys and zs using the filter function.
- ys is the list of elements less than x, and zs is the list of elements greater than or equal to x.
- We recursively sort ys and zs, and combine the two parts and pivot to create a sorted list. We will use list concatenation (++) to do this.
At the outset, the implementation looks like an exact qsort. However, a closer look reveals that we use the filter function to partition the elements in the list. The filter function is an O(n) function. In the worst case, ...