# Write insertion sort algorithm and its implementation. Also explain its time complexity.

- Written by Madhu V Rao
- Published in Programming Interview Questions for fresh Grads

Insertion sort is a basic sorting algorithm which works the way people sort a hand of playing cards.

Start with an empty left hand and then remove one card at a time from the deck and insert it into the correct position in your left hand.

lets start with the Pseudo code for Insertion sort algorithm.

input to the algorithm is an array A[1,2,...n] of length n.

Insertion sort is an in-place algorithm , i.e the sorting takes place within the array.

for j = 2 to A.length key = A[j] i = j - 1 while (i > 0 and A[i] > key) A[i+1] = A[i] i = i - 1 A[i+1] = key

Now , lets see the implementation in Java:

package com.example; public class Arrays { public static int[] insertionSort(int[] array) { int key = 0; int i = 0; for (int j = 1; j < array.length; j++) { key = array[j]; i = j - 1; while (i >= 0 && array[i] > key) { array[i + 1] = array[i]; i = i - 1; } array[i + 1] = key; } return array; } public static void main(String[] args) { int array[] = { 5, 3, 2, 1, 8, 9, 10 }; System.out.println("before sorting array = "); for (int e : array) { System.out.print(" " + e); } System.out.println("\nAfter sorting array = "); array = insertionSort(array); for (int e : array) { System.out.print(" " + e); } } }

Output:

before sorting array =

5 3 2 1 8 9 10

After sorting array =

1 2 3 5 8 9 10

Now, lets look into three cases , best , worst and average case:

Time complexity when array is already sorted (best case) is O(n) because second loop will never run

Worst case time complexity when array is completely unsorted is O(n*n).

Average case is also represented as O(n*n)

Similarly , Candidates can also be asked about bubble sort, Selection sort and asked to explain time complexity in best/worst/average case. Be prepared for such kind of questions.

Gud luck.