# 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]
```

**Explanation**:

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.