Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Java DSA implementation can be compared directly with the other languages.

Basic Implementation

Basic.java 
class Basic {
	public static void main(String[] args) {
		int[] arr = new int[] { 5, 1, 4, 2, 8 };
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = key;
		}
		printArray(arr);
	}

	static void printArray(int[] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if (i > 0) System.out.print(", ");
			System.out.print(arr[i]);
		}
		System.out.println("]");
	}
}

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • Java stores the sortable data in one primitive int[], allocated as new int[] { 5, 1, 4, 2, 8 }. The algorithm mutates that same array rather than creating a second output array or calling Arrays.sort.
  • The outer index loop starts at i = 1 and runs while i < arr.length. int key = arr[i] copies the current value into a local primitive before the shift loop overwrites array slots.
  • The shift loop uses j >= 0 && arr[j] > key as its bounds and comparison guard. Each arr[j + 1] = arr[j] copies a primitive value one slot right, then arr[j + 1] = key places the saved value.
  • The replay condenses the visible in-place mutations into shifts/placements: insert 1, shift 5 for 4, then shift 5 and 4 for 2. Aside from the initial array allocation, the sort uses local primitives and creates no ongoing JVM GC pressure.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.