## 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 with v)

```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 with v)

```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 with v)

```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 with v)

```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, v = v, v
```
```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] +  + 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, v = v, v
```
```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 with v)

```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, v = v, v
```
```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 +  + 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, v = v, v
```

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 with v)

```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, v = v, v
```

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[] +  + qsorted
```

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, v = v, v
```
```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.

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, v = v, v
```

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[] +  + qsorted[63, 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, 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, v = v, v
```
```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 with v)

```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.

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, v = v, v
```
```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 +  + qsorted
```

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, 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!