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.

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

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.

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

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.

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.

Now, key = 5, we need to sort 5 until it goes down to arr[1], let’s do that.

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.

Now key = 3, we will swap 9 and 3.

The same process goes on until 3 is in arr[1]

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.

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!