Recently I’ve been reviewing basic algorithms and data structures. I have one more year left of university and then I have to find a job. You hear all kind of crazy stories from programming interviews, but one recurring theme is algorithms and data structures. Long story, short; know them.
So, in this post we’ll take a look at insertion sort. One of the most basic sorting algorithms you’ll learn.
Insertion sort is a sorting algorithm that has a worst case of $O(n^2)$. It is one of the basic sorting algorithms that you would learn on a Computer Science course. Wikipedia has a good explanation of it.
This is an implementation of it that I wrote when following along to the CLRS book.
for j, val in enumerate(array):
key = array[j]
i = j - 1
while i >= 0 and array[i] > key:
array[i + 1] = array[i]
i = i - 1
array[i + 1] = key
I’ll be posting more implementations of basic algorithms and data structures in the future, so if you find this kind of post helpful, by all means subscribe to my posts feed and learn as I learn.