Implement Insertion Sort Editorial

Practice Problem Link: Implement Insertion Sort | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array, sort it using insertion sort.

Approach

In insertion sort, the basic idea is to divide the array into a sorted and an unsorted part. Elements from the unsorted part are picked one by one and placed at their correct position in the sorted part until the whole array is sorted.

• Iterate the array from i = 1 to i < n. Compare the i-th element to its previous elements one by one until it is less than its previous elements and keep moving the greater elements forward.
• Once the correct position for the i-th element is found (i.e. i-th element is greater than its previous element), place it at that position.

Analysis

• Time Complexity: O(n²)
• Auxiliary Space Complexity: O(1)

Implementation

C++

void insertionSort(vector<int> &arr) {
   int n = arr.size();
   for (int i = 1; i < n; i++) {
       int currentElement = arr[i];
       int position = i - 1;
       while (position >= 0 && arr[position] > currentElement) {
           arr[position + 1] = arr[position];
           position--;
       }
       arr[position + 1] = currentElement;
   }
}

Java

class Solution {
   void insertionSort (int[] arr) {
       int n = arr.length;
       for (int i = 1; i < n; i++) {
           int currentElement = arr[i];
           int position = i - 1;
           while (position >= 0 && arr[position] > currentElement){
               arr[position + 1] = arr[position];
               position--;
           }
           arr[position + 1] = currentElement;
       }
   }
}