Insertion Sort in Java
Problem
Insertion sort builds up a sorted section of the array one element at a time, sliding each new element backward into its correct position among the already-sorted elements before it.
Given an array of integers, sort it in ascending order using insertion sort.
Java Program
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 1, 9, 3, 7};
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// Shift every larger element rightward to open a gap for key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Treating the first element as already sorted, then repeatedly picking the next element and shifting it backward past every larger value before it, grows a sorted section one element at a time.
- 1The outer loop starts at index
1, since a single element is trivially sorted on its own. - 2
keyholds the value being inserted, andjstarts at the index just before it. - 3The inner
whileloop shifts each element rightward —arr[j + 1] = arr[j]— as long as it's greater thankey, opening up a gap. - 4Once the loop stops,
arr[j + 1] = keydrops the value into the gap it just opened — its correct sorted position.
[5, 1, 9, 3, 7], inserting 1 shifts 5 rightward and places 1 at the front, producing [1, 5, 9, 3, 7] — repeating this for each remaining element finishes the sort.Key Point: Unlike bubble or selection sort, insertion sort's inner loop doesn't always run to the end — it stops as soon as it finds an element that's already smaller than key, which is why it performs especially well on data that's already nearly sorted.
Why: The nested loops shift up to n elements per pass in the worst case, and each shift happens in place using only the key variable.