Insertion Sort

Idea

• The idea is to remove one entry at a time and insert it into the correct position in the sorted part.

Implementation

void insertionSort(int arr[]) {

int i, key, j;

for (i = 1; i < arr.length; i++){

key = arr[i];

j = i - 1;

// Move elements that are greater than key to the right by one position

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];

j = j - 1;

}

// insert the key to the head of the above elements

arr[j + 1] = key;

}

}

Time and Space Analysis

• Time O(n^2)
• Space O(1)