merge sort java error (learning from edX.org

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

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;
    }
}