Merge sort runs forever-CodePudding

I want to sort a 2d int array based on the 2nd element and this is what I came up with. But it doesnt seem to work. I understand there is a Arrays.sort(array, Comparator) which I can use, but I wanted to write my own sorting algorithm for the fun of it. Could anyone help me out please ?

ip = [[5,10],[2,5],[4,7],[3,9]]

Expected op = [[5,10],[3,9],[4,7],[2,5]]

void mergeSort(int[][] boxTypes){
    int mid = boxTypes.length / 2;
    int[][] left = new int[mid][2];
    int[][] right = new int[boxTypes.length - mid][2];
    
    for(int i = 0; i < mid; i  ) left[i] = boxTypes[i];
    for(int i = mid; i < boxTypes.length; i  ) right[i - mid] = boxTypes[i];
    
    mergeSort(left);
    mergeSort(right);
    
    merge(left, right, boxTypes);
}

void merge(int[][] left, int[][] right, int[][] boxTypes){
    int i = 0; int j = 0; int k = 0;
    
    while(i < left.length && j < right.length){
        if(left[i][1] < right[j][1]){
            boxTypes[k][0] = left[i][0];
            boxTypes[k][1] = left[i  ][1];
        } else {
            boxTypes[k][0] = right[j][0];
            boxTypes[k][1] = right[j  ][1];
        }
        k  ;
    }
    
    while(i < left.length) boxTypes[k  ] = left[i  ];
    while(j < right.length) boxTypes[k  ] = right[j  ];
}

CodePudding user response：

You never stop the recursion:

in the first step you split boxTypes into two arrays of length 2.
in the second step you split the first array of length 2 into two arrays of length 1.
in the third step you split the first array of length 1 into an array of length 0 and one of length 1.
in the fourth (and every succeeding step) you try to split the array of length 0 into two arrays of length zero.

You need to stop the recursion as soon as the length of boxTypes is 1 or less (since an array of length 0 or 1 is trivially sorted):

void mergeSort(int[][] boxTypes){
    if (boxTypes.length <= 1) return;
    int mid = boxTypes.length / 2;
    int[][] left = new int[mid][2];
    int[][] right = new int[boxTypes.length - mid][2];
    
    for(int i = 0; i < mid; i  ) left[i] = boxTypes[i];
    for(int i = mid; i < boxTypes.length; i  ) right[i - mid] = boxTypes[i];
    
    mergeSort(left);
    mergeSort(right);
    
    merge(left, right, boxTypes);
}

CodePudding user response：

There is an error in your while condition

while(i < left.length && j < right.length)

If i == left.length you don't check that j == right.length. So the remainig elements of boxTypes stay untouched.