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, the performance of our algorithm will be O(n2), a far cry from the qsort specifications.