# Insertion Sort Algorithm - Implementation in Java

In our previous blogs we came across many useful Algorithms and implementations in java. In this particular blog we will came across 'Insertion Sort Algorithm and its implementation in Java'.

Insertion Sort is a vary simple sorting algorithm, that best suits for sorting small data list and inserting a new value in a already sorted list. Although Insertion sort does not give better result in big data lists although for small data lists insertion sort is known as one of the best algorithm in respect to simplicity, stability and in place memory usage.

The motivation behind insertion sort is : "If some objects of a list are already sorted, than an unsorted object can be inserted in the sorted list in proper place. Insertion sort use no extra memory, it performs in place sorting".

## Insertion Sort Algorithm

Insertion sort algorithm takes one element in each  iteration and places it to the appropriate place in the sorted list of elements. In each iteration, it checks the value against all previous values and find a places the value should belongs to in a sorted manner. If  selected value is larger, it leaves the element in place and moves to the next element. If smaller, it finds the correct position within the sorted list, shifts all the larger values one step next to make a space, and inserts the selected element in correct position.

FOR j  2 TO length[A]
DO  key ← A[j]
{
Put A[j] into the sorted sequence A[1 . . j - 1]
}
i ← j - 1
WHILE i > 0 and A[i] > key
DO A[i +1] ← A[i]
i ← i - 1
A[i + 1] ← key

## Insertion sort implementation in Java

Insertion Sort implementation in java is very simple, we will iterate over a list to check each element and will compare it with all previous values in the sorted list. See the code below :

package com.beingjavaguys.sorting;

public class InsertionSortDemo {

/**
* @author Nagesh Chauhan
*/
public static void main(String[] args) {
int toSort[] = { 2, 4, 9, 6, 23, 12, 34, 0, 1 };

System.out.print("Array values BEFORE SORTING : ");
printValues(toSort); // array before sort

insertionSort(toSort); // sorting array using 'Insertion Sort Algorithm'

System.out.print("Array values AFTER SORTING  : ");
printValues(toSort); // array after sort
}

public static void insertionSort(int toSort[]) {
for (int i = 0; i < toSort.length; i++) {
int value = toSort[i];
int j = i - 1;
while (j >= 0 && toSort[j] > value) {
toSort[j + 1] = toSort[j];
j = j - 1;
}
toSort[j + 1] = value;

}
}

public static void printValues(int toSort[]) {
for (int k = 0; k < toSort.length; k++) {
System.out.print(toSort[k] + " ");

}
System.out.println();
}

}

## Insertion Sort Algorithm - Complexity Analysis

The best case scenario for Insertion Sort is when an input array is already sorted, in this case the algorithm has to only iterate over the list to check each element. No shifting will be made for a already sorted array, therefore Insertion Sort has a best case complexity of 'O(n)'.

The worst case scenario for Insertion Sort is when an input array is sorted in reverse order, in this case the algorithm has to iterate over the list to check each element. The shifting will be made after comparing each element to n elements, therefore Insertion Sort has a worst case complexity of 'O(n2)'.

The average case scenario for Insertion Sort can be considered when the input array has a large number of elements. Although Insertion sort is the fastest algorithm for small data lists even faster than 'Quick Sort', even good quick sort implementations uses Insertion Sort to sort arrays smaller than a certain threshold. It varies machine to machine but can be considered around 'O(n2)'.

In this particular blog we came across 'Insertion Sort Algorithm and it's Implementation in Java', in next tutorial we will see more about Java Algorithms and other opensource technologies.