Insertion Sort repeatedly removes an element from the input data and inserts it into the position so that its value is between the previous and the next element. It works the way we sort when playing cards. O(n 2) average and worst. Insertion sort is the best of simple sorting. For random data this algorithm runs twice as fast as the bubble sort and faster than selection sort.

Table of Content
What is insertion sort?
Insertion sort works the same way as we play cards. When we grad a new card from a deck, we insert it into the right place so that all cards in our hand are ordered. The time complexity is O(n 2) time.
How to implement insertion sort ?
Insertion sort uses a for loop to iterate through each element starting from index 1 in an array. Inside the loop, you use a while loop to check previous elements before the current item. Insert the current element in a position so that all elements before current position are sorted.
Insertion sort visualization

Insertion sort code
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import java.util.Arrays; public class InsertionSort { //Time O(n^2), Space O(1), n is array length public static void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int tmp = arr[i]; int j = i; while (j > 0 && arr[j-1] >= tmp ) { arr[j] = arr[j-1]; j--; } arr[j] = tmp; } } public static void main(String[] args) { int[] a = {19, 33, 4, 61, 5, 38, 36, 21, 0}; insertionSort(a); System.out.print("Insertion sort: "); System.out.println(Arrays.toString(a)); } } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Time O(n^2), Space O(1), n is array length function insertionSort(arr) { var n = arr.length; for (let i = 1; i < n; i++) { let tmp = arr[i]; let j = i; while (j > 0 && arr[j-1] >= tmp) { arr[j] = arr[j-1]; j--; } arr[j] = tmp; } } array = [19, 33, 4, 61, 5, 38, 36, 21, 0]; insertionSort(array); console.log("Insertion sort: "); console.log(array); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#Time O(n^2), Space O(1), n is array length def insertionSort(arr) : n = len(arr) for i in range( 1, n) : tmp = arr[i] j = i while j > 0 and arr[j-1] >= tmp : arr[j] = arr[j-1] j -= 1 arr[j] = tmp array = [19, 33, 4, 61, 5, 38, 36, 21, 0] insertionSort(array) print("Insertion sort: ") print(array) |
Free download
Download Java, JavaScript and Python code
Algorithm types and algorithm examples