Sensort - Learn Insertion Sort

A sorting algorithm which splits the input array in 2 parts, the sorted part and the unsorted part. In every iteration, the last element of the unsorted array is placed at its correct position in the sorted array.

Insertion Sort is a basic and simple sorting algorithm. It is named after the sorting technique used while arranging a deck of cards in the sorted order. Assume you have cards numbered 1, 3, 4, 5 in your hand and you want to place 2 in its correct position. You will make space for it by shifting 5 to the right, then 4, then 3 and then put 2 in its correct position i.e. after 1.

Insertion sort starts sorting the array from left to right. The first element of the array is assumed to be at the sorted position.

Characteristic	Value	Notes
Average Time Complexity	O(n²)	Same for worst case
Best Time Complexity	O(n)	For a sorted array
Space Complexity	O(1)	No extra storage required

Advantages:

Efficient sorting in best case, better than merge sort.

Disadvantages:

Inefficient for arrays with large input due to poor time complexity.

Implementation

Insertion sort should be easy to visualize from the animations. In every iteration the first bar of the unsorted array(red) is placed at its correct position(green) in the sorted array(pink). The logic of the bubble_sort() function is pretty simple, it works with 2 iterators:

itr_1: Holds the index of the end of sorted array after which the the unsorted array will begin
itr_2: Traverses the sorted array to find the correct position of the unsorted element by shifting all the elements greater than it to the right

> Initially, end of sorted array = 0^th index. And the traversal will begin from the first index of array to the last.
> Move itr_2 to the left and shift the element to the right if its value is greater than the unsorted element.
> For the first element whose value is lesser than the unsorted element, place the unsorted element on the right of that element.
> Repeat continuously for the next element of the unsorted array.

Code for the following in C++:

            
// function for insertion sort
void insertion_sort(int arr[], int n) {

	// i = itr_1 , j = itr_2
  for(int i = 1; i < n; ++i) {

	int unsorted = arr[i];
    int j = i - 1;

    // traverse the sorted array
    while(j >= 0 && arr[j] > unsorted) {
      arr[j + 1] = arr[j];
    }
    j++;

    arr[j] = unsorted;
  }
  
	return;
}