Learning Algorithms - Insertion Sort
Tags: computerscience, algorithms, insertion, python
Published: 2020-10-08 21:59:46

# Sorting
**Sorting** is one of the concepts of the basic algorithm as important as searching algorithms. There are tons of algorithms to sort items. Why do we need to sort elements? Because problems become easier once elements are sorted. For example, you can find a median in constant time when an array is sorted, meaning that you can use a binary search.

# Insertion Sort
If you think of the way to sort most easily in your head, it might be similar to **insertion sort**. How it works is, basically, it swaps pairs of elements from left to right until they are sorted. We will have a pointer called key that is a point starting from **1**.
```python
def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
```

![1_nOcET066RQ_fT6qpud24sQ](https://dev-to-uploads.s3.amazonaws.com/i/kcw1o7afcqsjz8z18qo3.png)
The code above looks like this visually.

**Key** will traverse from **1** all the way up to the end (n), and `j` points to **0** (index). **Key** will move to the right once **its left elements** are **sorted**. This rule can be expressed as follows.
```python
def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
        # as long as j is greater than or equals to 0 and left 
        # element(arr[j]) of key is bigger than key, 
        
        while j >= 0 and arr[j] > key:
           # swap: its left item will move to key
           arr[j + 1] = arr[j]
           # j moves down to the left
           j = j - 1
        # once all sorted, move elements 
        # where j stopped lastly
        arr[j + 1] = key
```

![1_Ksor4-KvDOox0P62yErqsg](https://dev-to-uploads.s3.amazonaws.com/i/3q7xea60donxsidz2jph.png)
We swapped `9` and `7` because they were unsorted. Because `7` and `9` are sorted, **move the key** to the **right** where there is `4`. Then compare `9` and `4`. `9` is greater than `4` but `4` is on the **left-hand side**, they should be swapped.

![1_Sl6mo4V8_-cMU3aESjIHBQ](https://dev-to-uploads.s3.amazonaws.com/i/5xvsdy8h2sfmnvpqok0q.png)
Move `4` down to the left **until it is sorted**. once a pair is swapped, `j` moves to the left. In this case, until 4 is placed in `arr[0]` (specifically on the code, when j becomes -1). Then move the key to the right where there is `5`.

![1_Bk8TZCDmJ4Ci4ip1f6vUcg](https://dev-to-uploads.s3.amazonaws.com/i/qwu9j6k7mnxgqi8ri509.png)
Now, `key = 5`, we need to sort `5` until it goes down to `arr[1]`, let’s do that.

![1_CvTKGj4hbE3tKQVAfNt3sw](https://dev-to-uploads.s3.amazonaws.com/i/o4cylhm07ab23uyiuckq.png)
 

![1_HyQUytuClGP5_jh6ksvMMg](https://dev-to-uploads.s3.amazonaws.com/i/3s4r9i2r6g8226086twg.png)
Because **key** (`4`) is sorted, move on to elements, the key becomes **1**(`arr[4]`). Keep swapping until 1 is sorted. Then the result will be like below.

![1_0V2AMej_19VWP8_8xN0lZA](https://dev-to-uploads.s3.amazonaws.com/i/jk5v8sl491bnlmba285n.png)
Now `key = 3`, we will swap `9` and `3`.

![1_wPLIbvHiPPVn-Fl-ajPRvQ](https://dev-to-uploads.s3.amazonaws.com/i/hv31gnf7s1mrn00ue0oh.png)
The same process goes on until `3` is in `arr[1]`

![1_4Ng8qzuUyahS4Iw9ZHjlvw](https://dev-to-uploads.s3.amazonaws.com/i/hyeozep5d5t7r5l11r45.png)
Finally, here we are! All elements in the array are _sorted_. 


# Time Complexity of Insertion Sort
Now, it is time to talk about the time complexity of the algorithms. As you might assume, it took so long time for us to get here. In a nutshell, the algorithm is **O(n²)**. Let’s analyse why.

![1_zvmD6Bgv792T2XEmxZGC6w](https://dev-to-uploads.s3.amazonaws.com/i/ro2ilqzyiq8lpryxlsut.png)
  
As you can see, (2)*O(1) and (2)*O(N) and (2)*O(N). We can actually ignore the coefficient. Therefore, the time complexity would be 1*N*N = N²

In conclusion, the time complexity of insertion is **quadratic time**, which is not very efficient. There is a faster way to sort elements though. I will introduce one later. Thanks for reading!