Sorting fundamentals #4: Insertion sort

Photo by Kelly Sikkema on Unsplash

What is insertion sort?

In insertion sort, we split the original array into 2 portions: sorted and unsorted. Insertion sort works by repeatedly inserting elements from the unsorted sub-array into a sorted portion of the array.

Insertion sort is best suited for small arrays. Insertion sort is used in Tim Sort( Python) and Intro Sort

Insertion sort performance

• Time complexity: O(n²)
• Space complexity: O(1)

Implementation of insertion sort

void insertion_sort(int[] arr, int n) {
  for(int i = 1; i < n - 1; i++) {
    int key = arr[i];
    int j = i - 1;
    while (arr[j] > key && j >= 0) {
      arr[j+1] = arr[j];
      j-=1;
    }
    arr[j+1] = key;
  }
}

Subscribe to my Medium: https://medium.com/@exploreintellect/subscribe