Implementing merge sort in Java: Only zeroes

Question

I'm trying to implement some sorting algorithms in Java working on int-arrays as an educational process. I currently try to wrap my head around merge sort. Yesterday I got pretty far, with a result of an array of the correct size, but only containing zeroes. Today I started new from the ground, and now I'm stuck at the same point. ^^ Here is my code:

public static int[] mergeSort(int[] array) {
    if (array.length < 2) {
        return array;
    }
    int left = 0;
    int right = array.length;
    int p = array.length / 2;
    int[] lArray = Arrays.copyOfRange(array, left, p);
    int[] rArray = Arrays.copyOfRange(array, p, right);
    lArray = mergeSort(lArray);
    rArray = mergeSort(rArray);
    return merge(lArray, rArray);
}

private static int[] merge(int[] lArray, int[] rArray) {
    int[] result = new int[lArray.length + rArray.length];
    int idx = 0;
    int rIdx = 0;
    int lIdx = 0;
    while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1) {
        if (lArray[lIdx] < rArray[rIdx]) {
            result[idx] = lArray[lIdx];
            lIdx++;
        } else if (lArray[lIdx] >= rArray[rIdx]) {
            result[idx] = rArray[rIdx];
            rIdx++;
        }
        idx++;
    }
    if (lIdx < (lArray.length - 1)) {
        result[idx] = lArray[lIdx + 1];
    } else if (rIdx < (rArray.length - 1)) {
        result[idx] = rArray[rIdx + 1];
    }
    return result;
}

I think it's pretty OKly-styled and readable. So, all you algorith- and Java-cracks out there, what am I missing? Debugging points toward the merge method, but I can't quite pin it down, so I publish this as-is.

Thanks in advance!


Show source
| java   | sorting   | algorithm   | mergesort   2017-01-06 14:01 3 Answers

Answers to Implementing merge sort in Java: Only zeroes ( 3 )

  1. 2017-01-06 14:01
    if (lIdx < (lArray.length - 1)) {
        result[idx] = lArray[lIdx + 1];
    } else if (rIdx < (rArray.length - 1)) {
        result[idx] = rArray[rIdx + 1];
    }
    

    This part is a bit strange. Why do you just copy one remaining element into your result array? You should copy all the remaining elements from either lArray or rArray into your result. Use 'while' instead of 'if'.

  2. 2017-01-06 14:01

    I see two issues in your merge method :

    First of all, your while loop ignores the last element of the left and right arrays. You should change

    while (lIdx < lArray.length - 1 && rIdx < rArray.length - 1)
    

    to

    while (lIdx < lArray.length && rIdx < rArray.length)
    

    Second of all, After that while loop, you need two more while loops to add the tail of the left array or the tail of the right array. Instead you only add a single element.

    Replace

    if (lIdx < (lArray.length - 1)) {
        result[idx] = lArray[lIdx + 1];
    } else if (rIdx < (rArray.length - 1)) {
        result[idx] = rArray[rIdx + 1];
    }
    

    with

    while (lIdx < lArray.length) {
        result[idx++] = lArray[lIdx++];
    } 
    while (rIdx < rArray.length) {
        result[idx++] = rArray[rIdx++];
    }
    
  3. 2017-01-06 14:01

    Here you go

    public class MergeSort {
    
    public static int[] mergeSort(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int left = 0;
        int right = array.length;
        int p = array.length / 2;
        int[] lArray = Arrays.copyOfRange(array, left, p);
        int[] rArray = Arrays.copyOfRange(array, p, right);
        //printArray(lArray); seems ok
        //printArray(rArray); seems ok
        lArray = mergeSort(lArray);
        rArray = mergeSort(rArray);
        return merge(lArray, rArray);
    }
    
    private static int[] merge(int[] lArray, int[] rArray) {
        /*System.out.println("Ive got");
        printArray(lArray);
        printArray(rArray); seems ok*/
        int[] result = new int[lArray.length + rArray.length];
        int index = 0;
        int rightIndex = 0;
        int leftIndex = 0;
        while (leftIndex < lArray.length && rightIndex < rArray.length) { //TODO
            if (lArray[leftIndex] < rArray[rightIndex]) {
                result[index] = lArray[leftIndex];
    
                leftIndex++;
                index++;
                //} else if (lArray[leftIndex] >= rArray[rightIndex]) { // You don't have to check it!!!
            } else {
                System.out.println("2 left index " + leftIndex + " index " + index);
                result[index] = rArray[rightIndex];
                rightIndex++;
                index++;
            }
        }
        while (leftIndex < (lArray.length)) { // TODO
            result[index] = lArray[leftIndex];
            index++;
            leftIndex++;
        }
        while (rightIndex < (rArray.length)) { // TODO
            result[index] = rArray[rightIndex];
            index++;
            rightIndex++;
        }
        System.out.println("Returning ");
        printArray(result);
        return result;
    }
    
    public static void printArray(int[] arr) {
        for (int i : arr)
            System.out.print(i + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 1, 3, 4, 0, -1};
        printArray(arr);
        arr = mergeSort(arr);
        printArray(arr);
    }
    }
    

    What was wrong is marked with //TODO

Leave a reply to - Implementing merge sort in Java: Only zeroes

◀ Go back