Sorting - Insertion Sort

Implement the Insertion Sort algorithm. Build the sorted array one element at a time by inserting each element into its correct position.

Input: [12, 11, 13, 5, 6] → Output: [5, 6, 11, 12, 13]

Input: [31, 41, 59, 26, 41, 58] → Output: [26, 31, 41, 41, 58, 59]

For each element from index 1 to n-1, shift larger elements one position right and insert the current element in its correct position.

Start with index i = 1; treat arr[0..i-1] as sorted.
Save key = arr[i]; shift elements greater than key one position to the right.
Place key in the gap created.
Repeat for all elements. Efficient for nearly-sorted data.

class InsertionSort { public void sort(int[] arr) { int n = arr.length; for (int i = 1; i < n; 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; } } }

Time Complexity: O(N^2) worst, O(N) best
Space Complexity: O(1) in-place