Insertion Sort

1public void insertionSort(int[] arr) {
2    int n = arr.length;
3
4    for (int i = 1; i < n; i++) {
5        int key = arr[i];
6        int j = i - 1;
7
8        while (j >= 0 && arr[j] > key) {
9            arr[j + 1] = arr[j];
10            j--;
11        }
12
13        // Insert key at the correct position
14        arr[j + 1] = key;
15    }
16}