```
In [ ]:
```%%HTML
<style>
.container { width:100% }
</style>

The basic idea of *quick sort* is as follows:

- If the list $\mathtt{L}$ that is to be sorted is empty, we return $\mathtt{L}$: $$ \mathtt{sort}([]) = L $$
Otherwise, we have $\mathtt{L} = [\mathtt{x}] + \mathtt{R}$. In this case, we split $\mathtt{R}$ into two lists $\mathtt{S}$ and $\mathtt{B}$.

- The list $\mathtt{S}$ (the letter $\mathtt{S}$ stands for $\underline{s}\textrm{mall}$) contains all those elements of $\mathtt{R}$ that are less or equal than $\mathtt{x}$, we have: $$ \mathtt{S} := [\mathtt{y} \in \mathtt{R} \mid \mathtt{y} \leq \mathtt{x}] $$
- The list $\mathtt{B}$ (the letter $\mathtt{B}$ stands for $\underline{b}\textrm{ig}$) contains those elements of $\mathtt{R}$ that are bigger than $\mathtt{x}$, we have: $$ \mathtt{B} := [\mathtt{y} \in \mathtt{R} \mid \mathtt{y} > \mathtt{x}] $$

The process of splitting the list $\mathtt{R}$ into the lists $\mathtt{S}$ and $\mathtt{B}$ is called

*partitioning*. After partitioning the list $\mathtt{R}$ into the lists $\mathtt{S}$ and $\mathtt{B}$, these lists are sorted recursively. Then, the result is computed by putting $\mathtt{x}$ between the lists $\mathtt{sort}(\mathtt{S})$ and $\mathtt{sort}(\mathtt{B})$: $$\mathtt{sort}([\mathtt{x}|\mathtt{R}]) = \mathtt{sort}(\mathtt{S}) + [\mathtt{x}] + \mathtt{sort}(\mathtt{B})$$

```
In [ ]:
```def sort(L):
if L == []:
return L
x, R = L[0], L[1:]
S = [y for y in R if y <= x]
B = [y for y in R if y > x]
return sort(S) + [x] + sort(B)

```
In [ ]:
```sort([7, 8, 11, 12, 2, 5, 3, 7, 9, 3, 2])

```
In [ ]:
```