Search code examples
javamergesort

Merge-Sort implementation / suspecting mistake in recursive call or while merging


any help with this mess is appreciated. The task here is to sort an array of integers that differ from zero. I think i made two mistakes which i cant manage to solve.

first: i think i made a mistake at the recursive call. The bounds seem to be set the wrong way while merging

second: i also think the sorting process has several errors too

    static void mergeSort(int[] init, int lower, int upper) {
    if (lower < upper) {

        int mid = (lower + upper) / 2;
        mergeSort(init, lower, mid);
        mergeSort(init, mid+1, upper);
        merge(init, lower, mid, upper);
    }
}

static void merge(int[] init, int lower, int mid, int upper) {
    int length1 = mid - lower;      //length of first subarray
    int length2 = upper - mid;      //length of second subarray

    int[] leftArray = new int[length1+1];     //creating left subArray
    int[] rightArray = new int[length2+1];    //creating right subArray

    for (int i = 0; i < length1; i++) {       //copying positions from left partition to left subArray
        leftArray[i] = init[lower + i];
    }

    for (int i = 0; i < length2; i++) {       //copying positions from right partition to right subArray
        rightArray[i] = init[mid+i];
    }

    int i = 0;                                //sorting
    int j = 0;
    for (int k = lower; k < upper; k++) {
        if (leftArray[i] <= rightArray[j]) {
            init[k] = leftArray[i];
            i++;
        } else {
            init[k] = rightArray[j];
            j++;
        }
    }
}

Solution

  • Wasn't this the recommended way to do the merge sort step-by-step using static methods:

    public static void mergeSort(int[] init, int arrayLength) {
        if (arrayLength < 2) {
            return;
        }
        int mid = arrayLength / 2;
        int[] left = new int[mid];
        int[] right = new int[arrayLength - mid];
     
        for (int i = 0; i < mid; i++) {
            left[i] = init[i];
        }
        for (int i = mid; i < arrayLength; i++) {
            right[i - mid] = init[i];
        }
        mergeSort(left, mid);
        mergeSort(right, arrayLength - mid);
     
        merge(init, left, right, mid, arrayLength - mid);
    }
    
    public static void merge(
      int[] init, int[] left, int[] right, int leftLength, int rightLength) {
     
        int i = 0, j = 0, k = 0;
        while (i < leftLength && j < rightLength) {
            if (left[i] <= right[j]) {
                init[k++] = left[i++];
            }
            else {
                init[k++] = right[j++];
            }
        }
        while (i < leftLength) {
            init[k++] = left[i++];
        }
        while (j < rightLength) {
            init[k++] = right[j++];
        }
    }
    

    Call "mergeSort" with the 1st parameter being the array to be sorted and the 2nd parameter being it's length.

    Cheers!