Why is my insertion sort failing this test case?

Question

I'm trying to write an insertion sort, and I pass several test cases, but I fail one. My code is:

static void insertionSort1(int n, int[] arr) {


    int copy = arr[n-1];

    int i = n - 1;
    while (copy < arr[i-1]){

        arr[i] = arr[i-1];

        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + " ");
        }
            System.out.println();
        i--;
        }
     arr[i] = copy;
    for(int m = 0; m < arr.length; m++){
       System.out.print(arr[m] + " ");
     }
    }

where n is the size of the array, and arr is the array. My algo fails this test case in particular:

10

2 3 4 5 6 7 8 9 10 1

I get index out of bounds on that but not on

5

2 4 6 8 3

or others. what's going on?

Answer 1

That is an index out of bound exception of the array because of minus value of the arr. It is not an algorithm issue but a language.

while (i > 0 && copy < arr[i - 1])

Source:

public class InsertionSort {
    static void insertionSort1(int n, int[] arr) {

        int copy = arr[n - 1];

        int i = n - 1;
        while (i > 0 && copy < arr[i - 1]) {

            arr[i] = arr[i - 1];

            for (int k = 0; k < arr.length; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
            i--;
        }
        arr[i] = copy;
        System.out.println("#### RESULT ####");
        for (int m = 0; m < arr.length; m++) {
            System.out.print(arr[m] + " ");
        }
        System.out.println("\n#### END ####\n");
    }

    public static void main(String[] args)
    {
        //10
        //2 3 4 5 6 7 8 9 10 1
        int[] arr ={2, 3, 4, 5, 6, 7, 8, 9, 10, 1};
        int n = arr.length;
        insertionSort1(n, arr);


        //5
        //2 4 6 8 3
        arr= new int[5];
        n = arr.length;

        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 8;
        arr[4] = 3;

        insertionSort1(n, arr);
    }
}

Result:

2 3 4 5 6 7 8 9 10 10 
2 3 4 5 6 7 8 9 9 10 
2 3 4 5 6 7 8 8 9 10 
2 3 4 5 6 7 7 8 9 10 
2 3 4 5 6 6 7 8 9 10 
2 3 4 5 5 6 7 8 9 10 
2 3 4 4 5 6 7 8 9 10 
2 3 3 4 5 6 7 8 9 10 
2 2 3 4 5 6 7 8 9 10 
#### RESULT ####
1 2 3 4 5 6 7 8 9 10 
#### END ####

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
#### RESULT ####
2 3 4 6 8 
#### END ####

Have a good day.