A Walkthrough Example of QuickSort

Quicksort, Slowly

Starting with an array:

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}5 \end{array} \]

We first set the values \(low\) and \(high\) that determine the subset of the array in which we'll be working. With this being the first pass, \(low\) will be \(0\) and \(high\) will be \(length - 1\).

We then ask the return condition.

Is \(low \geq high\) ?

No! We've only just started! But this would be \(true\) if the length of the array was \(0\) or \(1\) because an array of length \(0\) or \(1\) is always sorted. We'd then return, breaking the cycle.

We need to find where our first split will be. This will be around the \(pivot\).

We'll set \(pivot\) to \(array[high]\). For now, that's the last item in the array.

We'll also set \(index\) to \(low - 1\).

\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

We'll then loop through the array, from \(low\) to \(high\).

Start!

\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}0}}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}4}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}4}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

No!

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}4}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}6}& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

No!

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}1}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]

Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

The item at \(pivot\) is now sorted.

The array is now split at \(pivot\).

Items to the left are all less than or equal to \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underline{\underset{\hphantom{index}}0}& \underline{\underset{\hphantom{index}}4}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underline{\underset{\hphantom{index}}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Items to the right are all greater than \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underline{\underset{\hphantom{index}}7}& \underline{\underset{\hphantom{index}}6} \end{array} \]

We'll branch off to the left first.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

No!

Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).

\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Start!

\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}0}}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}4}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

No!

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

No!

Next Item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

No!

Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

The item at \(pivot\) is now sorted.

The array is now split at \(pivot\).

Items to the left are all less than or equal to \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underline{\underset{\hphantom{index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Items to the right are all greater than \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underline{\underset{\hphantom{index}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

We'll continue down this path, branching off to the left first.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

Yes! This item is already sorted!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

We'll branch off to the right now.

With \(pivot\ index + 1\) as \(low\), go again!

Is \(low \geq high\) ?

No!

Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Start!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}2}}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Next item!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}3}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}4}}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

The item at \(pivot\) is now sorted.

The array is now split at \(pivot\).

Items to the left are all less than or equal to \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}4}}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Normally, there would be a second branch where the items to the right are all greater than \(pivot\). Though, in this case, the pivot is the last item in the subset and there are no items to the right! So there is only the branch to the left.

We'll continue down this path.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

No!

Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Start!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Is \(item \leq pivot\) ?

Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}2}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}3}}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

The item at \(pivot\) is now sorted.

The array is now split at \(pivot\).

Items to the left are all less than or equal to \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underline{\underset{\hphantom{index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}3}}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

There is no right branch.

We'll continue down this path.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

Yes! This item is already sorted!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]

We've finished the original left branch! Let's move on to the right.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

No!

Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}6} \end{array} \]

Start!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}5}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}6} \end{array} \]

Is \(item \leq pivot\) ?

No!

Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}6}}& \underset{\hphantom{index}}7 \end{array} \]

The item at \(pivot\) is now sorted.

The array is now split at \(pivot\).

There is no left branch.

Items to the right are all greater than \(pivot\).

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}6}}& \underline{\underset{\hphantom{index}}7} \end{array} \]

We'll continue down this path.

With \(pivot\ index - 1\) as \(high\), go again!

Is \(low \geq high\) ?

Yes! This item is already sorted!

\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\color{green}6}& \underset{\hphantom{index}}{\color{green}7} \end{array} \]

All Finished!

We can visualize the result as a tree:

Write it in Python!

                        # quicksort.py
                        import time
                        from typing import List

                        def quicksort(array: List[int]) -> List[int]:
                            def _quicksort(array: List[int], low: int, high: int):
                                if low >= high:
                                    return

                                pivot_index = _partition(array, low, high)

                                _quicksort(array, low, pivot_index-1)
                                _quicksort(array, pivot_index+1, high)

                            def _partition(array: List[int], low: int, high: int) -> int:
                                pivot = array[high]
                                index = low - 1
                                for item in range(low, high):
                                    if array[item] <= pivot:
                                        index += 1
                                        temp = array[item]
                                        array[item] = array[index]
                                        array[index] = temp

                                index += 1
                                array[high] = array[index]
                                array[index] = pivot

                                return index

                            _quicksort(array, 0, len(array)-1)
                            return array

                        array = [0, 4, 8, 2, 3, 7, 6, 1, 5]
                        start_time = time.time()
                        sorted_array = quicksort(array[:])
                        print(f'{array} → {sorted_array} in {(time.time() - start_time) * 1000:.3f}ms')

                        $ python quicksort.py
                        [0, 4, 8, 2, 3, 7, 6, 1, 5] → [0, 1, 2, 3, 4, 5, 6, 7, 8] in 0.018ms

0.018ms?! Maybe we'll let the computer handle it from now on...