# Sorting Algorithms in Python — Insertion Sort

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).