## Quicksort in Excruciating Detail

13 Nov 2017

Let's take this slice of ints:

6, 63, 58, 24, 54, 28, 33, 80, 100

and try to qsort them.

func QSort(v []int, left int, right int) { last := 0 if left >= right { return } v[left], v[(left+right)/2] = v[(left+right)/2], v[left] last = left for i := left + 1; i <= right; i++ { if v[i] < v[left] { last++ v[last], v[i] = v[i], v[last] } } v[left], v[last] = v[last], v[left] QSort(v, left, last-1) QSort(v, last+1, right) }

It's interesting to note that the function needs to be called with the first and last index of our slice in addition to the slice itself! You'd think you could just call QSort(mySlice) and be done with it.

When we think about it, that makes sense, because for QSort to be able to work recursively, we need to be able to tell it to work on smaller and smaller ranges of the underlying slice, and to do that, we need to be able to call it with the starting and ending indices.

So if our above slice of ints is assigned to a varable v, we call QSort like so:

QSort(v, 0, len(v)-1)

QSort first call:

v: [6, 63, 58, 24, 54, 28, 33, 80, 100] left: 0 right: 8 last: 0

So we definitely get past this:

if left >= right { return }

Now we chose the pivot from the middle and swap it to the start of the slice:

v[left], v[(left+right)/2] = v[(left+right)/2], v[left]

As near as I can tell, this is in case the list is sorted; we then take the pivot that would be the best pivot to use for a sorted slice. It's interesting that we pick the pivot and then put it at the start of the array. I *think* this might make other implementation details easier, because then you have the pivot out of the way while you walk the remaining array looking for (and swapping) values that are less than the pivot. But I'm not sure.

So now our slice looks like this:

v: [54, 63, 58, 24, 6, 28, 33, 80, 100]

6 and 54 have swapped places.

Now we assign the left index to last:

left: 0 right: 8 last: 0

last will be the last index of the slice on our left. It will increment every time we swap a value smaller than the pivot into a new slice index, and we will feed it to a recursive call to QSort later.

Note that our for loop does not start at left, it starts at left + 1, so that we don't disturb the pivot that's all the way left.

Now we read the slice from left +1 to right, and whenever an item is larger than our pivot (located in v[left] we put it in the next available slot in the left part of the slice (which is why we increment last when the swap needs to happen):

if v[i] < v[left] { last++ v[last], v[i] = v[i], v[last] }

So the iteration looks like this:

left: 0 right: 8 last: 0 i: 1 v: [54, 63, 58, 24, 6, 28, 33, 80, 100] i right

63 is not less than 54, so next loop, increment i.

left: 0 right: 8 last: 0 i: 2 v: [54, 63, 58, 24, 6, 28, 33, 80, 100] i right

58 is not less than 54, so next loop, increment i.

left: 0 right: 8 last: 0 i: 3 v: [54, 63, 58, 24, 6, 28, 33, 80, 100] i right

24 is less than 54, so increment last and swap v[i] with v[last] (swap v[3] with v[1])

left: 0 right: 8 last: 1 i: 3 v: [54, 24, 58, 63, 6, 28, 33, 80, 100] last i right

next loop, increment i.

left: 0 right: 8 last: 1 i: 4 v: [54, 24, 58, 63, 6, 28, 33, 80, 100] last i right

6 is less than 54, so increment last and swap v[i] with v[last] (swap v[4] with v[2])

left: 0 right: 8 last: 2 i: 4 v: [54, 24, 6, 63, 58, 28, 33, 80, 100] last i right

next loop, increment i.

left: 0 right: 8 last: 2 i: 5 v: [54, 24, 6, 63, 58, 28, 33, 80, 100] last i right

28 is less than 54, so increment last and swap v[i] with v[last] (swap v[5] with v[3])

left: 0 right: 8 last: 3 i: 5 v: [54, 24, 6, 28, 58, 63, 33, 80, 100] last i right

next loop, increment i.

left: 0 right: 8 last: 3 i: 6 v: [54, 24, 6, 28, 58, 63, 33, 80, 100] last i right

33 is less than 54, so increment last and swap v[i] with v[last] (swap v[5] with v[3])

left: 0 right: 8 last: 4 i: 6 v: [54, 24, 6, 28, 33, 63, 58, 80, 100] last i right

next loop, increment i.

left: 0 right: 8 last: 4 i: 7 v: [54, 24, 6, 28, 33, 63, 58, 80, 100] last i right

80 is not less than 54, so next loop, increment i.

left: 0 right: 8 last: 4 i: 8 v: [54, 24, 6, 28, 33, 63, 58, 80, 100] last i right

100 is not less than 54, so next loop, increment i.

left: 0 right: 8 last: 4 i: 9 v: [54, 24, 6, 28, 33, 63, 58, 80, 100] last i right

Break out of loop because i, 9, is greater than right, 8.

Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.

v[left], v[last] = v[last], v[left] v[0], v[4] = v[4], v[0]

left: 0 right: 8 last: 4 v: [33, 24, 6, 28, 54, 63, 58, 80, 100] left last right

With the pivot, 54, at its correct final index in the slice, the correctly sorted slice would look like

qsorted[33, 24, 6, 28] + [54] + qsorted[63, 58, 80, 100]

So that looks like

QSort(v, left, last-1) QSort(v, last+1, right)

Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.

In other words:

QSort(v, 0, 3) // let's call this QSort L1 QSort(v, 5, 8) // Let's call this QSort R1

Continuing on with the call, L1, to QSort(v, 0, 3):

left: 0 right: 3 last: 0 v: [33, 24, 6, 28, 54, 63, 58, 80, 100]

left is not greater than or equal to right, so we pass this:

if left >= right { return }

We swap the middle index, our pivot, with the left-most index:

v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[0], v[1] = v[1], v[0]

left: 0 right: 3 last: 0 v: [24, 33, 6, 28, 54, 63, 58, 80, 100] right

We make last equal to left:

left: 0 right: 3 last: 0 v: [24, 33, 6, 28, 54, 63, 58, 80, 100] right

Now we enter our loop, with i starting at left + 1:

left: 0 right: 3 last: 0 i: 1 v: [24, 33, 6, 28, 54, 63, 58, 80, 100] i right

33 is not less than 24, so next loop, increment i.

left: 0 right: 3 last: 0 i: 2 v: [24, 33, 6, 28, 54, 63, 58, 80, 100] right i

6 is less than 24, so increment last and swap v[i] with v[last] (swap v[2] with v[1])

left: 0 right: 3 last: 1 i: 2 v: [24, 6, 33, 28, 54, 63, 58, 80, 100] right i last

next loop, increment i.

left: 0 right: 3 last: 1 i: 3 v: [24, 6, 33, 28, 54, 63, 58, 80, 100] right i last

28 is not less than 24, so next loop, increment i.

left: 0 right: 3 last: 1 i: 4 v: [24, 6, 33, 28, 54, 63, 58, 80, 100] right i last

Break out of loop because i, 4, is greater than right, 3.

Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.

v[left], v[last] = v[last], v[left] v[0], v[1] = v[1], v[0]

left: 0 right: 3 last: 1 v: [6, 24, 33, 28, 54, 63, 58, 80, 100] left right last

With the pivot, 24, at its correct final index in the slice, the correctly sorted sub slice would look like

qsorted[6] + [24] + qsorted[33, 28]

So that looks like

QSort(v, left, last-1) QSort(v, last+1, right)

Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.

In other words:

QSort(v, 0, 0) // let's call this QSort L2 QSort(v, 2, 3) // Let's call this QSort R2

Continuing on with the call, L2, to QSort(v, 0, 0):

left is equal to right, so we return from this:

if left >= right { return }

Continuing on with the call, R2, to QSort(v, 2, 3):

left is not greater than or equal to right, so we pass this:

if left >= right { return }

We swap the middle index, our pivot, with the left-most index:

v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[2], v[2] = v[2], v[2]

The interesting thing being our numbers are now so close together that we just swapped the first value with itself!

left: 2 right: 3 last: 0 v: [6, 24, 33, 28, 54, 63, 58, 80, 100] left right

We make last equal to left:

left: 2 right: 3 last: 2 v: [6, 24, 33, 28, 54, 63, 58, 80, 100] left right last

Now we enter our loop, with i starting at left + 1:

left: 2 right: 3 last: 2 i: 3 v: [6, 24, 33, 28, 54, 63, 58, 80, 100] left right last i

28 is less than 33, so increment last and swap v[i] with v[last] (swap v[3] with v[2])

left: 2 right: 3 last: 2 i: 3 v: [6, 24, 28, 33, 54, 63, 58, 80, 100] left right last i

next loop, increment i.

left: 2 right: 3 last: 2 i: 4 v: [6, 24, 28, 33, 54, 63, 58, 80, 100] left right last i

Break out of loop because i, 4, is greater than right, 3.

Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.

v[left], v[last] = v[last], v[left] v[3], v[3] = v[3], v[3]

Again, because our numbers are so close together, we swap the pivot with itself!

left: 2 right: 3 last: 2 v: [6, 24, 28, 33, 54, 63, 58, 80, 100] left right last

With the pivot, 24, at its correct final index in the slice, the correctly sorted sub sub slice would look like

qsorted[] + [24] + qsorted[28]

So that looks like

QSort(v, left, last-1) QSort(v, last+1, right)

Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.

In other words:

QSort(v, left, last-1) QSort(v, last+1, right)

Continuing on with the call, L3, to QSort(v, 2, 1):

left is greater than right, so we return from this:

if left >= right { return }

Continuing on with the call, R3, to QSort(v, 3, 3):

left is equal to right, so we return from this:

if left >= right { return }

Continuing on with the call, R1, to QSort(v, 5, 8):

left: 5 right: 8 last: 0 v: [6, 24, 28, 33, 54, 63, 58, 80, 100]

left is not greater than or equal to right, so we pass this:

if left >= right { return }

We swap the middle index, our pivot, with the left-most index:

v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[5], v[6] = v[6], v[5]

left: 5 right: 8 last: 0 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right

We make last equal to left:

left: 5 right: 8 last: 5 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last

Now we enter our loop, with i starting at left + 1:

left: 5 right: 8 last: 5 i: 6 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last i

63 is not less than 58, so next loop, increment i.

left: 5 right: 8 last: 5 i: 7 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last i

80 is not less than 58, so next loop, increment i.

left: 5 right: 8 last: 5 i: 8 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last i

100 is not less than 58, so next loop, increment i.

left: 5 right: 8 last: 5 i: 9 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last i

Break out of loop because i, 9, is greater than right, 8.

v[left], v[last] = v[last], v[left] v[5], v[5] = v[5], v[5]

Here, because everything was larger than the pivot, we end up swapping the pivot with itself, leaving it where it was!

left: 5 right: 8 last: 5 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last

With the pivot, 58, at its correct final index in the slice, the correctly sorted sub slice would look like

qsorted[] + [58] + qsorted[63, 80, 100]

So that looks like

QSort(v, left, last-1) QSort(v, last+1, right)

In other words:

QSort(v, 5, 4) // let's call this QSort L4 QSort(v, 6, 8) // Let's call this QSort R4

Continuing on with the call, L4, to QSort(v, 5, 4):

left is greater than right, so we return from this:

if left >= right { return }

Continuing on with the call, R1, to QSort(v, 6, 8):

left: 6 right: 8 last: 0 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right

left is not greater than or equal to right, so we pass this:

if left >= right { return }

We swap the middle index, our pivot, with the left-most index:

v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[6], v[7] = v[7], v[6]

left: 6 right: 8 last: 0 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right

We make last equal to left:

left: 6 right: 8 last: 6 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right last

Now we enter our loop, with i starting at left + 1:

left: 6 right: 8 last: 6 i: 7 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right last i

63 is less than 80, so increment last and swap v[i] with v[last] (swap v[7] with v[7])

left: 6 right: 8 last: 6 i: 7 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right last i

next loop, increment i.

left: 6 right: 8 last: 6 i: 8 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right last i

100 is not less than 80, so next loop, increment i.

left: 6 right: 8 last: 6 i: 9 v: [6, 24, 28, 33, 54, 58, 80, 63, 100] left right last i

Break out of loop because i, 9, is greater than right, 8.

v[left], v[last] = v[last], v[left] v[6], v[7] = v[7], v[8]

left: 6 right: 8 last: 6 v: [6, 24, 28, 33, 54, 58, 63, 80, 100] left right last

With the pivot, 80, at its correct final index in the slice, the correctly sorted sub slice would look like

qsorted[63] + [80] + qsorted[100]

So that looks like

QSort(v, left, last-1) QSort(v, last+1, right)

In other words:

QSort(v, 6, 6) // let's call this QSort L5 QSort(v, 8, 8) // Let's call this QSort R5

Continuing on with the call, L5, to QSort(v, 6, 6):

left is equal to right, so we return from this:

if left >= right { return }

Continuing on with the call, R5, to QSort(v, 8, 8):

left is equal to right, so we return from this:

if left >= right { return }

DONE!