Posted on by & filed under algorithms, programming, python, Tech.

My wife and I are avid board gamers, but oddly one of the the things we enjoy most is organizing the game itself. We’ve often joked about buying a game just to organize it. I love the “pop” as the chits break free from their cardboard bonds; discovering how each piece looks and sorting them according to size, shape and color; figuring out how to put the pieces back in the box without having any of them break before the next time we play the game.

I think this love of tidiness is also what draws me to algorithms and sorting algorithms in particular. You start with a jumbled array of items and by following some simple steps you arrive at something organized, something that makes sense.

## Insertion Sort

Average Complexity: O(n^2)
Advantages: Small footprint and fairly quick for small datasets.

The insertion sort is probably the simplest sorting algorithm. It’s actually very similar to what most people do when they’re handed a deck of cards and are asked to sort them.

An insertion sort is done by building a sorted array in place. For each element, compare it to the elements before it. If it’s larger or the same it stays where it is. If it’s smaller it gets swapped with all the elements before it until it’s either the first element or it’s larger or equal to the element before it.

## Mergesort

Average Complexity: O(n log(n))

Mergesort is a divide-and-conquer algorithm. It splits the input data until it has a single element list for each item in the input and then recursively merges these together in sorted order.

Python’s sort methods use a variant called timsort which is essentially a hybrid of mergesort and insertion sort.

## Quicksort

Average Complexity: O(n log(n))
Advantages: In practice it’s faster than mergesort and has a smaller memory footprint.

Quicksort works by picking an element in the array to be the pivot, and then dividing all the other elements in the array into two arrays. One contains items that are smaller than the pivot; the other contains items that are larger. Recursion is then used to sort the subdivided array.

Python implementation

## Heap Sort

Average Complexity: O(n log(n))
Advantages: In most cases it’s slower than Quicksort, but it has a better worst-case running time.

Heap sort is interesting when compared to the other three algorithms here, in that it actually doesn’t use an array as its data structure, it uses a heap. A heap is type of priority queue, generally created as a binary tree where any given node always has a higher priority (in the case of sorting, a smaller number) than its children.

Once you have a heap, returning a sorted array is very simple, you just keep popping off the root node until the tree is empty. This can also be done much simpler by using Python’s built-in heapq.

### Python implementation

#### Step-by-step

Input: [4, 3, 5, 2, 1]