MergeSort. Error in merging logic

Question

Can anyone say what is the problem in the merging logic? If element of right array is less than element in left array then it works. Other wise gives wrong answer. I have divided the array properly. I am giving my merging logic here.

public static void main(String[] args) {
    int[] list = { 32,14, 67, 76, 23, 41, 58, 85};
    System.out.println("before: " + Arrays.toString(list));
    mergeSort(list);
    System.out.println("after:  " + Arrays.toString(list));
}

public static void mergeSort(int[] array) {
    if (array.length > 1) {
        // split array into two halves
        int[] left = leftHalf(array);
        int[] right = rightHalf(array);

        mergeSort(left);
        mergeSort(right);

        merge(array, left, right);

    }
}


public static void merge(int[] result,
        int[] left, int[] right) {
    int i1 = 0;   // index into left array
    int i2 = 0;   // index into right array
    int j = 0;
    int k = 0;
    for (int i=0; i1 < left.length && i2 < right.length;i++) {
        if (left[i1] < right[i2]) {
            result[i] = left[i1];
            // take from left
            i1++;
        } else {
            result[i] = right[i2];
            // take from right
            i2++;
        }
    }
}

After the for-loop, did you forget to copy the remaining part of one subarray back to result, when the other subarray reaches the end? — waltersu, Jun 08 '16 at 07:56
Duplication of http://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array — Sergei Rybalkin, Jun 08 '16 at 08:18

score 0 · Answer 1 · answered Jun 08 '16 at 08:58

You've got two unused variables j and k in your code. Your logic is flawed because you copy into the array until one half is empty, so you never actually empty both halves.

public static void merge(int[] result, int[] left, int[] right) {
    int i1 = 0;   // index into left array
    int i2 = 0;   // index into right array
    int i;
    for (i = 0; i1 < left.length && i2 < right.length;i++) {
        if (left[i1] < right[i2]) {
            result[i] = left[i1++];
            // take from left
        } else {
            result[i] = right[i2++];
            // take from right
        }
    }
    for (; i1 < left.length; i++) result[i] = left[i1++];
    for (; i2 < right.length; i++) result[i] = right[i2++];
}

Only one of the two for loops will run at the end, and will process what's left of the other half.

Thanks. Solved it. I did not copied the remaining subarray. – Jun 08 '16 at 14:16 — , Jun 08 '16 at 14:16

MergeSort. Error in merging logic

1 Answers1