So Much Sorting

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.