I put on my sorting hat and watched many, many videos on sorting.

The videos covered:

- bubble sort
- selection sort
- insertion sort
- heap sort
- merge sort
- quicksort
- counting sort
- radix sort

There are several more sorting algorithms I could have gone into, but I had to stop somewhere. I'd like to learn about bitonic sort, signature sort, etc. So I added another few videos to the sorting section that I'll get around to.

What I really like about sorting is the terse code needed to do something very powerful. Even though comparison-based sorting theoretically can't do better that O(n log n), that's pretty darn good. Given the right constraints, such as all your keys to sort are the same length and a small k (for digits, 0..9), you can switch to radix sort and rock O(n) sorting.

Want to see some code?

### Merge Sort

Merge sort requires O(n) additional space.

```
namespace jw {
void merge(int numbers[], int low, int mid, int high) {
// temp array for holding sorted items
int b[high - low - 1];
int i = low;
int j = mid + 1;
int k = 0;
// merge items from list in order
while (i <= mid && j <= high) {
if (numbers[i] <= numbers[j]) {
b[k++] = numbers[i++];
} else {
b[k++] = numbers[j++];
}
}
// copy the remaining items to tmp array
while (i <= mid) b[k++] = numbers[i++];
while (j <= high) b[k++] = numbers[j++];
--k;
while (k >= 0) {
numbers[low + k] = b[k];
--k;
}
}
void merge_sort(int numbers[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
merge_sort(numbers, low, mid);
merge_sort(numbers, mid + 1, high);
merge(numbers, low, mid, high);
}
}
} // namespace jw
```

### Quicksort

Note this uses random pivot selection, and sorts in-place.

```
import random
class QuickSort(object):
def __init__(self, numbers):
self.values = numbers
self.count = len(self.values)
def sort(self):
self.quick_sort(0, self.count - 1)
return self.values
def quick_sort(self, left, right):
if left == right:
return
i = left
j = right
pivot_index = random.randint(left, right)
pivot = self.values[pivot_index]
while i <= j:
while self.values[i] < pivot:
i += 1
while self.values[j] > pivot:
j -= 1
if i <= j:
if i < j:
temp = self.values[i]
self.values[i] = self.values[j]
self.values[j] = temp
i += 1
j -= 1
if left < j:
self.quick_sort(left, j)
if right > i:
self.quick_sort(i, right)
```

And here are some notes. I take lots of notes.