Insert Sort

static void insertSort(int[] arr, int n) {
    if (n <= 1) {
        return;
    }

    insertSort(arr, n - 1);


    int j = n - 2;
    int tail = arr[j + 1];

    while (j >= 0 && arr[j] > tail) {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = tail;
}