Insertion Sort in Java

Insertion Sort Steps are as follows:

• In the begining step the leftmost number is considered fully sorted.
• Next step, from the remaining numbers the leftmost number is taken out and compared to the already sorted numbers to its left side.
• If the already sorted number is larger than current number, swap the two numbers.
• Repeat the operation until a smaller number identified, or the number reaches the left end.
• The same steps are repeated until all the numbers are fully sorted.

The Insertion sort is approximately double faster from the Bubble sort algorithm.

---

Insertion Sort Complexities

Time Complexity

---

Best Case = O(n)

Average Case = O(n²)

Worst Case = O(n²)

---

Space Complexity = O(1)

---

Sample Code in Java for Insertion Sort Algorithm

InsertionSortTest.java class

package com.learning.algorithm.insertionSort;

public class InsertionSortTest {

	private long[] inputValuesArray; // reference to array
	private int items; // number of data items

	/*
	 * Parameterized constructor of InsertionSortTest class
	 */
	public InsertionSortTest(int max) {
		inputValuesArray = new long[max]; // create an array with provided value
		items = 0; // set data items to zero
	}
	
	/*
	 * perform insert sorting on unsorted data 
	 */
	public void insertSort() {
		int outerLoop, innerVal;

		System.out.println("Unsorted Input Values.... ");
		display(); 																		// print unsorted array values once

		for (outerLoop = 1; outerLoop < items; outerLoop++) { 							// iterate the loop in forward order
			
			Long currentOuterLoopValue = inputValuesArray[outerLoop];					// select value to compare
			innerVal = outerLoop;														// assign outerLoop index to innerLoop  
			
			while(innerVal > 0 && inputValuesArray[innerVal-1] >= currentOuterLoopValue) {// until innerLoop values are small
				
				inputValuesArray[innerVal] = inputValuesArray[innerVal-1];
				
				-- innerVal;															//move one position left
			}
			System.out.println("\ninserted " + currentOuterLoopValue + " in the position of " + inputValuesArray[innerVal]);
			
			inputValuesArray[innerVal] = currentOuterLoopValue;							// insert the selected value

			display();
		}
	}


	
	/*
	 * insert the value into the array
	 */
	public void insert(long value) {
		inputValuesArray[items] = value; // insert the value in array
		items++; // increment size
	}

	/*
	 * display the array contents
	 */
	public void display() {
		for (int j = 0; j < items; j++) // iterate for each element
			System.out.print(inputValuesArray[j] + " \t"); // print the value
		System.out.println("");
	}


}

---

InsertionSortMain.java class

package com.learning.algorithm.insertionSort;

public class InsertionSortMain {

	public static void main(String[] args) {
		int maxSize = 50; // array max size
		InsertionSortTest insertionSortTest; // reference to InsertionSortTest
		insertionSortTest = new InsertionSortTest(maxSize); // create the InsertionSortTest array with maximum size
		insertionSortTest.insert(65); // insert some values into InsertionSortTest array
		insertionSortTest.insert(01);
		insertionSortTest.insert(00);
		insertionSortTest.insert(54);
		insertionSortTest.insert(21);
		insertionSortTest.insert(52);
		insertionSortTest.insert(19);
		insertionSortTest.insert(57);
		insertionSortTest.insert(18);
		insertionSortTest.insert(16);
		insertionSortTest.insertSort(); // perform insertion sorting on inserted data
	} 
}

Output of the sample Java program

# Unsorted Input Values.... 
65 	1 	0 	54 	21 	52 	19 	57 	18 	16 	

# inserted 1 in the position of 65
1 	65 	0 	54 	21 	52 	19 	57 	18 	16 	

# inserted 0 in the position of 1
0 	1 	65 	54 	21 	52 	19 	57 	18 	16 	

# inserted 54 in the position of 65
0 	1 	54 	65 	21 	52 	19 	57 	18 	16 	

# inserted 21 in the position of 54
0 	1 	21 	54 	65 	52 	19 	57 	18 	16 	

# inserted 52 in the position of 54
0 	1 	21 	52 	54 	65 	19 	57 	18 	16 	

# inserted 19 in the position of 21
0 	1 	19 	21 	52 	54 	65 	57 	18 	16 	

# inserted 57 in the position of 65
0 	1 	19 	21 	52 	54 	57 	65 	18 	16 	

# inserted 18 in the position of 19
0 	1 	18 	19 	21 	52 	54 	57 	65 	16 	

# inserted 16 in the position of 18
0 	1 	16 	18 	19 	21 	52 	54 	57 	65