Insertion Sort works the way we sort playing cards. Each iteration removes an element from the input data and inserts it into the correct position. 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.
Source 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) |
Doodle
Download Java, JavaScript and Python code
Insertion sort animated