Insertion sort is an easy algorithm. The running time of the algorithm depends on the number of the elements that’s why it is not very efficient. The logic is simple, start with second element and compare it to previous element and swap them if needed, continue comparing same second element till you reach the beginning of the array. Iterate all the elements till the end of the array.

Java code snippet

public static int[] insertionSort(int[] array) {
	for(int i = 1; i < array.length; i++) {	//start with second element
		for(int j = i - 1; j >= 0 && array[j] > array[j + 1]; --j) { //compare to previous element and continue swapping till the start
			swap(array, j, j + 1);
		}
	}
	return array;
}
public static void swap (int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Complexity analysis

Best: O(n)

Worst: O(n^2)

Dima Svirid

Software architect, JAVA, Spring, Hibernate, AngularJs, Backbone, MongoDB, Oracle. CTO and Co-Founder of Homeadnet.com

More Posts

Follow Me:

Tagged with: