Insertion Sort

Share

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

Example 1
Input: [12, 11, 13, 5, 6] → Output: [5, 6, 11, 12, 13]
Example 2
Input: [31, 41, 59, 26, 41, 58] → Output: [26, 31, 41, 41, 58, 59]

Solution Approach

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.
Java
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