A Quick One on Quicksort

Stare at this program until you understand it.

qsort[] = []
qsort(x:xs) = qsort smaller ++ [x] ++ qsort larger where
    smaller = [a | a <- xs, a <= x]
    larger  = [b | b <- xs, b > x]


qsort is a function that takes one argument. Let’s assume this argument is going to be a list of numbers. If the given argument is an empty list, an empty list is returned, as seen on the first line. If the given list is not empty, we’ll move on to the second line.

x refers to the head of the given list.

xs (the s is conventionally used here to denote it being plural with respect to x) refers to the tail of the list, the two being separated by a colon. x and xs may be named anything you wish, for example head and tail.

Given the list, [1, 2, 3, 4], the head (x) of the list is 1 and the tail (xs) of the list is the list, [2, 3, 4].

qsort is first recursively called on smaller. A function call (the following example with 3 arguments) has the pattern:

functionName arg1 arg2 arg3

You’ll notice there are no commas and each part is separated by a space, for example: qsort larger calls the qsort function while passing larger as it’s first and only argument.

smaller is created by something called a list comprehension. The full line may be read as, “smaller is equal to a list containing a some 'a's, such that each a is 'a' member of the list, xs, and each 'a' is also smaller than or equal to x.”

An optional exercise would be to try and think out-loud in the same way for how larger is created on the line below.

The now recursively sorted smaller list is concatenated (++) with a list containing only x, the head of the original list, which in turn is concatenated with the also now sorted list, larger.

larger is created in the same way as smaller but instead requires that it's members', the 'b's, to each be be greater than x.

smaller will end up containing all numbers smaller than or equal to x, which in turn will themselves be sorted due to the recursive calls, while larger will contain all numbers larger than x, again, sorted.