Haskell Cookbook

How it works...

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, ...