merge sort java error (learning from edX.org

Question

This is the array I want to merge sort, located in static void main:

int[] lst = {6, 5, 4, 7, 2, 1, 9}

Here's the mergeSort function:

static int[] mergeSort(int[] lst) {
    int n = lst.length; 
    int[] left;
    int[] right;

    // create space for left and right subarrays
    if (n % 2 == 0) {
        left = new int[n/2];
        right = new int[n/2];
    } 
    else {
        left = new int[n/2];
        right = new int[n/2+1];
    }

    // fill up left and right subarrays
    for (int i = 0; i < n; i++) {
        if (i < n/2) {
            left[i] = lst[i];
        }
        else {
            right[i-n/2] = lst[i];
        }
    }

    // **ERROR B**

    // recursively split and merge
    left = mergeSort(left);
    right = mergeSort(right);

    // merge
    return merge(left, right);
}

Here is the merge function:

// the function for merging two sorted arrays
static int[] merge(int[] left, int[] right) {
    // create space for the merged array
    int[] result = new int[left.length+right.length];

    // running indices
    int i = 0;
    int j = 0;
    int index = 0;

    // add until one subarray is deplete
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result[index++] = left[i++];
        { // **ERROR A** [ see description below ]
        else {
            result[index++] = right[j++];
        }
    }

    // add every leftover elelment from the subarray 
    while (i < left.length) {
        result[index++] = left[i++];
    }

    // only one of these two while loops will be executed
    while (j < right.length) {
        result[index++] = right[j++];
    }

    return result;
}

ERROR A: I get an error here saying else statement with no if. If I delete the curly brace under result[index++] = left[i++] it will run and give me a error of: Exception in thread "main" java.lang.StackOverflowError and point the error to code above which is ERROR B.

Here's the source code

Answer 1

This is very close. All you're missing is your recursive base case in your merge sort, which, as written, will endlessly recurse until the stack blows. It says: "List of 0 or 1 items? Keep splitting!"

Merge sort's key realization is that a single-element array or zero-element array is already sorted. This is the base case. Code it as follows:

if (n <= 1) {
    return lst; // this list is already sorted
}

As for your other error, that's just a mismatched bracket and fixing it should give you the stack overflow error, which was your main issue and was unrelated to the bracket issue. Here's complete working code:

class Main {
    public static void main(String[] args) {
        int[] lst = {6, 5, 4, 7, 2, 1, 9};
        System.out.println(java.util.Arrays.toString(mergeSort(lst)));
    }

    static int[] mergeSort(int[] lst) {
        int n = lst.length; 

        if (n <= 1) {
            return lst;
        }

        int[] left;
        int[] right;

        if (n % 2 == 0) {
            left = new int[n/2];
            right = new int[n/2];
        } 
        else {
            left = new int[n/2];
            right = new int[n/2+1];
        }

        for (int i = 0; i < n; i++) {
            if (i < n / 2) {
                left[i] = lst[i];
            }
            else {
                right[i-n/2] = lst[i];
            }
        }
        
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length+right.length];
        int index = 0;
        int i = 0;
        int j = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[index++] = left[i++];
            }
            else {
                result[index++] = right[j++];
            }
        }

        while (i < left.length) {
            result[index++] = left[i++];
        }

        while (j < right.length) {
            result[index++] = right[j++];
        }

        return result;
    }
}