Insertion sort | Java JavaScript Python

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²) 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²) 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

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));
}
}

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

//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);

//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

#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)

#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

Login

Insertion sort – code and visuals