Insertion Sort

Intro

Insertion sort is one of the three famous algorithms (Bubble Sort, Selection Sort, and Insertion Sort) that have a time complexity of O(n^2), which means it is not a fast sorting algorithm.

Let's see how it works and its implementation.

Insertion Sort - how does it work?

This algorithm works just like we would sort the playing cards in our hands. We divide the array into sorted and unsorted parts, and we begin with the first element of the unsorted part, and compare it with elements of the sorted part - elements on the left.

For each element on the left (starting from the right side of the sorted array) we check if the element is greater than the current element, if yes, we move to the next element in the sorted array until we find an element that is not greater than the current element. In that case, we stop iterating and move all the elements that are greater one position to the right, so that we can make room for the new element, that we are holding at the moment. 

After every iteration, we put the element at its correct position inside the sorted part.

Let's code it

Below is the Java implementation of the algorithm

public class InsertionSort {

public void sort(int[] arr) {

for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j] = temp;
}
}
}

At the beginning, we start from position 1, because we need to have the first element inside the sorted part, so that we can compare the second element to it and put it into the corresponding spot.

We also need to have the variable temp - to avoid possible overriding of the arr[i];

The variable i points to the element at the unsorted part, while the variable j points to the element of the sorted part. 

In the while loop. we decrease the j by 1 since we are comparing elements from right to left until we find the element from the sorted part that is smaller than the current element from the unsorted part.

Here is the illustration of the unsorted and sorted parts of the array, and how we are moving and comparing the elements.

You see, the sorted array is on the left, and unsorted on the right. So we compare the first element of the unsorted part with the elements of the sorted part, starting from right to left, because we want to stop when we find the element that is smaller than the element held by the variable temp.
Then, we just move the greater elements to one position on the right, to put the value from the temp variable at the correct spot.

Insertion sort - analysis

The worst case and average case are both O(n^2), while the best case is O(n).

Worst case and Average case O(n^2) - When the array is not sorted or sorted in reverse order. In that case, a lot of comparations and swapping will occur.

Best case O(n) - In case the array is already sorted, the insertion sort compares O(n) elements and performs no swaps, and the while inner loop never gets triggered.

Space complexity is always O(1) and it is a stable sorting algorithm.