Java Using a Merge Sort to sort an Array of Numbers

Question

I'm trying to use a merge sort in Java to sort an array of numbers. In this case the array is numBars. I made a small array of 30 numbers and have attached the output from the console. I track the merge method to see why I'm getting an index issue. I believe that I am off by 1 somewhere, but can't seem to figure out where my logic is going haywire.

public void mergeSort() {
        mergeSortHelper(numBars, 0);
        System.out.println(Arrays.toString(numBars));
    }

    public void mergeSortHelper(int[] theArray, int leftIndex) {

        //split the list in half
        int mid = theArray.length/2;
        if (mid < 1) {
            return;
        } else {
            System.out.println("Left Index is originally: " + leftIndex);
            int[] left = Arrays.copyOfRange(theArray, 0, mid);
            int[] right = Arrays.copyOfRange(theArray, mid, theArray.length);
            //sort the lower half
            mergeSortHelper(left, leftIndex);
            mergeSortHelper(right, leftIndex + left.length);
            //merge them together
            merge(left, right, leftIndex);
            System.out.println("Left Index is now: " + leftIndex);
            System.out.println("Right Index is now: " + (leftIndex + mid));
            System.out.println(Arrays.toString(numBars));
            left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid);
            right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length);
        }
    }

    public void merge(int[]a, int[]b, int leftIndex) {
        int i = 0;
        int j = 0;
        int result = leftIndex;
        while (i < a.length && j < b.length) {
            //System.out.println("Comparing from A: " + a[i] + " Comparing from B: " + b[i]);
            if (a[i] < b[j]) {
                theCanvas.wait(theDelay);
                theCanvas.eraseRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]);
                numBars[result] = a[i];
                result++;
                theCanvas.fillRectangle(graphWidth + i * barWidth, graphHeight - barScale * numBars[i], barScale, barScale * numBars[i]);
                i++;
            } else {
                theCanvas.wait(theDelay);
                theCanvas.eraseRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]);
                numBars[result] = b[j];
                result++;
                theCanvas.fillRectangle(graphWidth + j * barWidth, graphHeight - barScale * numBars[j], barScale, barScale * numBars[j]);
                j++;

            }
            //System.out.println("First Loop, Comparing Size" + Arrays.toString(output));
        }
        while (i < a.length) {
            numBars[result] = a[i];
            result++;
            i++;
            //System.out.println("Second Loop, Finishing A array" + Arrays.toString(output));
        }

        while(j < b.length) {
            numBars[result] = b[j];
            result++;
            j++;
            //System.out.println("Third Loop, Finishing B array" + Arrays.toString(output));
        }
        //System.out.println(Arrays.toString(output));
    }

CONSOLE OUTPUT:

Left Index is originally: 0
Left Index is originally: 0
Left Index is originally: 0
Left Index is originally: 1
Left Index is now: 1
Right Index is now: 2
[10, 50, 55, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 0
Right Index is now: 1
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 3
Left Index is originally: 3
Left Index is now: 3
Right Index is now: 4
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 5
Left Index is now: 5
Right Index is now: 6
[10, 55, 50, 18, 99, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 3
Right Index is now: 5
[10, 55, 50, 9, 46, 99, 18, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is now: 0
Right Index is now: 3
[10, 55, 50, 99, 18, 9, 46, 80, 37, 35, 69, 77, 34, 53, 53]
Left Index is originally: 7
Left Index is originally: 7
Left Index is originally: 7
Left Index is now: 7
Right Index is now: 8
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53]
Left Index is originally: 9
Left Index is now: 9
Right Index is now: 10
[10, 55, 50, 99, 18, 9, 46, 37, 80, 35, 69, 77, 34, 53, 53]
Left Index is now: 7
Right Index is now: 9
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 77, 34, 53, 53]
Left Index is originally: 11
Left Index is originally: 11
Left Index is now: 11
Right Index is now: 12
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53]
Left Index is originally: 13
Left Index is now: 13
Right Index is now: 14
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 34, 77, 53, 53]
Left Index is now: 11
Right Index is now: 13
[10, 55, 50, 99, 18, 9, 46, 35, 69, 80, 37, 53, 53, 77, 34]
Left Index is now: 7
Right Index is now: 11
[10, 55, 50, 99, 18, 9, 46, 77, 34, 53, 53, 80, 37, 35, 69]
Left Index is now: 0
Right Index is now: 7
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46]
[10, 55, 50, 80, 37, 35, 69, 77, 34, 53, 53, 99, 18, 9, 46]

Any help would be greatly appreciated! Thanks!

This would be easier if you tell us which line is throwing the exception. — madth3
– madth3, Commented Dec 11, 2012 at 0:39
@madth3 Problem is, it's not throwing an exception. Here's what's happening though, in a merge sort, the original array, numBars is split into arrays left and right recursively, and then left and right are put back into place into numBars, this last part about putting it back into numBars is where I'm getting all the problems. — Vikram
– Vikram, Commented Dec 11, 2012 at 0:46
Can you post your main method? Also, just a curiosity, but what is the meaning behind the name numBars? — The111
– The111, Commented Dec 11, 2012 at 0:55

Daniel Fischer · Accepted Answer · 2012-12-11 00:57:08Z

} else {
    System.out.println("Left Index is originally: " + leftIndex);
    int[] left = Arrays.copyOfRange(theArray, 0, mid);
    int[] right = Arrays.copyOfRange(theArray, mid, theArray.length);
    //sort the lower half
    mergeSortHelper(left, leftIndex);
    mergeSortHelper(right, leftIndex + left.length);
    //merge them together
    merge(left, right, leftIndex);
    System.out.println("Left Index is now: " + leftIndex);
    System.out.println("Right Index is now: " + (leftIndex + mid));
    System.out.println(Arrays.toString(numBars));
    left = Arrays.copyOfRange(numBars, leftIndex, leftIndex + mid);
    right = Arrays.copyOfRange(numBars, leftIndex + mid, leftIndex + mid + right.length);
}

At the end, when you're copying values from numBars into left and right, that is entirely pointless, because these go out of scope immediately afterward and will be garbage collected.

In the caller, the array that that should sort, remains unchanged. You need to copy the merged values from numBars into the array theArray that is the argument, so that when the caller merges, it merges sorted arrays.

So replace the last two lines in the else block with

for(int i = 0; i < mid; ++i) {
    theArray[i] = numBars[leftIndex + i];
}
for(int i = mid; i < mid + left.length; ++i) {
    theArray[i] = numBars[leftIndex + i];
}

to copy the merge result into the same object that the caller passed.

It would, however, lead to much cleaner code, if you passed the array in which the merge result should be placed as an argument to merge.

yeah correctly pointed out so....after merging subarrays you are not returning them as already sorted arrays.

Collectives™ on Stack Overflow

Java Using a Merge Sort to sort an Array of Numbers

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related