This is the first of a series of posts about sorting algorithms. I’m going to start with the dumbest of all: Insertion Sort.
I will try, for each post of this series, to follow this schema:
- Brief description of how the algorithm works
- Python implementation
- Execution time graph
How Insertion Sort works
Insertion Sort is a sorting algorithm that follows an incremental approach, in fact it orders one element at a time. To have a clear idea about how it works here is a pretty explanatory GIF:
Since this is the first post I am going to briefly explain how the complexity of an algorithm is defined. The study of an algorithm in terms of asymptotic efficiency is expressed in function of the number of the inputs (in this case the number of the values to order) through three notations:
- Ω
- O
- Θ
Ω Notation
Given a function g(n) then Ω(g(n)) denotes the set of functions f(n) such as for every n greater than n0 and for every c (positive constant):
So g(n) represents an asymptotic lower bound for f(n).
O Notation
Given a function g(n) then O(g(n)) denotes the set of functions f(n) such as for every n greater than n0 and for every c (positive constant):
So g(n) represents an asymptotic higher bound for f(n).
Θ Notation
Given a function g(n) then Θ(g(n)) denotes the set of functions f(n) such as for every n greater than n0 and for every c1, c2 (positive constants):
So g(n) represents an asymptotic tight bound for f(n).
Algorithm Overview
Best-case complexity: O(n)
Worst-case complexity: O(n²)
Stable: Yes (if there are two elements with the same value their relative order will be kept)
In-place: Yes (There is a maximum number of elements saved outside the array, in this case just one)
Python Implementation
Here is the Python implementation:
If you want to see the source code you can check my GitHub!
Conclusions
So if Insertion Sort is so stupid, slow, and ugly why should we use it?
It’s very simple: we do not.
There are plenty of sorting algorithms and Insertion Sort is rarely used and only if the size of the array is very small (in this case it behaves not-so-bad and it is convenient because it is very easy to implement).
