Insertion Sort Algorithm
Insertion sort algorithm is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
This works like the way we sort playing cards in our hands.

Performance
- Worst-case performance :- О(n2) comparisons, swaps
- Best-case performance :- O(n) comparisons, O(1) swaps
- Average performance :- О(n2) comparisons, swaps
- Worst-case space complexity :- О(n) total, O(1) auxiliary
Java Program of Insertion Sort Algorithm
0 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
package cn.algo.sorting; public class InsertionSort { void insertionSort(int inputArr[]) { int n = inputArr.length; for (int j = 1; j < n; j++) { int key = inputArr[j]; int i = j-1; while ( (i > -1) && ( inputArr[i] > key ) ) { inputArr[i+1] = inputArr[i]; i--; } inputArr[i+1] = key; } } /* Printing sorted array */ void printArray(int inputArr[]) { int n = inputArr.length; for (int i = 0; i < n; ++i) System.out.print(inputArr[i] + " "); System.out.println(); } public static void main(String args[]) { InsertionSort obj = new InsertionSort(); int inputArr[] = { 80,15,60,30,20,90 }; System.out.println("Input Array before Insertion Sort."); obj.printArray(inputArr); obj.insertionSort(inputArr); System.out.println("\nSorted Array after Insertion Sort."); obj.printArray(inputArr); } } |
Output
Some theory part of this article uses material from the Wikipedia article “Insertion Sort”, which is released under the CC BY-SA 3.0.