Merge sort implementation questions in Java

Question

I'm in an algorithms course and am learning about merge sort. Our professor recommended we try to implement the pseudo code provided in the book.

Am I correct in using Integer.MAX_VALUE as a sentinel value when sorting an array of integers (used in lines 8 & 9 in the Merge method pseudo code below)?
For line 2 of the Merge-Sort pseudo code method, is it correct to code that in Java using Math.ceil() like I did? (Edit: It's actually floor and I updated my code to reflect this.)

If you see any other mistakes please let me know!

Here is the pseudo code the book gives for merge sort.

And, here is how I coded it in Java:

public void mergeSort(int[] arrNums, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(arrNums, p, q);
        mergeSort(arrNums, q + 1, r);
        merge(arrNums, p, q, r);
    }
}

public void merge(int[] arrNums, int p, int q, int r) {
    int nOne = q - p + 1;
    int nTwo = r - q;

    int[] arrLeft = new int[nOne + 1];
    int[] arrRight = new int[nTwo + 1];

    for (int i = 0; i < nOne; i++) {
        arrLeft[i] = arrNums[p + i - 1];
    }

    for (int j = 0; j < nTwo; j++) {
        arrRight[j] = arrNums[q + j];
    }

    arrLeft[nOne] = Integer.MAX_VALUE;
    arrRight[nTwo] = Integer.MAX_VALUE;

    // Tracks arrLeft index
    int i = 0;

    // Tracks arrRight index
    int j = 0;

    for (int k = p; k < r; k++) {
        if (arrLeft[i] <= arrRight[j]) {
            arrNums[k] = arrLeft[i];
            i++;
        } else {
            arrNums[k] = arrRight[j];
            j++;
        }
    }
}

That's not ceil in the pseudo code, it's floor. And if you operate on integers, that's implied anyway. — Maarten Bodewes
– Maarten Bodewes, Commented Apr 1, 2017 at 23:27
An alternative to using infinity.. is to check if the left or right arrays has no more variables, then you dumb the remainder of the another one into the main array. — Shady Atef
– Shady Atef, Commented Apr 1, 2017 at 23:33
In most libraries, a variation of bottom up merge sort is more common. Wiki has simple examples of top down and bottom up merge sort for arrays and linked lists. Wiki merge sort. Usually there's a one time allocation of a working array the same (or 1/2) the size of the original array, and the direction of merge alternates with iteration pass or in the case of top down merge sort with level of recursion (this avoids unnecessary copying of data). — rcgldr
– rcgldr, Commented Apr 2, 2017 at 7:45

shizhz · Accepted Answer · 2017-04-02 00:17:40Z

2

The last for loop in your merge method, variable k should start from p - 1:

for (int k = p - 1; k < r; k++) {
    if (arrLeft[i] <= arrRight[j]) {
        arrNums[k] = arrLeft[i];
        i++;
    } else {
        arrNums[k] = arrRight[j];
        j++;
    }
}

Pseudo code in many text books likes to start array index from 1, so here you need to subtract it by 1.

answered Apr 2, 2017 at 0:17

shizhz

12.7k4 gold badges44 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sheldonzy · Accepted Answer · 2017-08-20 13:53:55Z

I implemented it a few days ago, if someone will be interested.

private static void mergeSort(double[] arr, int start, int end){
    if(start < end){
        int mid = ( start + end ) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }
}


private static void Merge(double[] arr, int start, int mid, int end){

    double[] leftArray = new double[mid - start + 2];
    double[] rightArray = new double[end - mid + 1];
    for(int i = start; i <= mid; i++ )
        leftArray[i - start] = arr[i];
    for (int i = mid + 1; i <= end; i++ )
        rightArray[i - mid - 1] = arr[i];

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY;
    rightArray[end - mid] = Double.POSITIVE_INFINITY;

    int leftIndex = 0, rightIndex = 0;

    for (int k = start; k <= end; k++){
        if(leftArray[leftIndex] <= rightArray[rightIndex])
            arr[k] = leftArray[leftIndex++];
        else
            arr[k] = rightArray[rightIndex++];
    }   
}

Collectives™ on Stack Overflow

Merge sort implementation questions in Java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related