MergeSort problems

Question

I tried to put MergeSort into code (see below). The problem is: it doesn't sort correctly in any case. 55,6% (of 1000 random Arrays) are sorted correctly, the rest ist not. I cannot figure out whats wrong. Any help/hints would be appreciated:

import java.util.Arrays;
    public class MergeSort {
        public static void sort(int[] a){
            if (a.length > 1){
                int[] left = Arrays.copyOfRange(a,0,a.length/2);
                int[] right = Arrays.copyOfRange(a,a.length/2,a.length);
                sort(left);
                sort(right);
                a = merge(left,right);
            }
     }

    private static int[] merge (int[] a, int[] b){
        int[] c = new int[a.length+b.length];
        int i = 0, j=0, k=0;

        while ((i < a.length) && (j <b.length)){
            if (a[i] < b[j]) c[k++] = a[i++];
            else c[k++] = b[j++];
        }
        while (i<a.length) c[k++] = a[i++];
        while (j<b.length) c[k++] = b[j++];                                         
    return c;
    }

}

I think you understand, that I would not ask this question, if I was (at this point in time) able to solve the problem myself with debugging. But I can give some arrays, which are NOT sorted by my code: 4, 2, 7, 5, 2, 3, 0, 4, 6, 2 7, 6, 7, 1, 1, 7, 1, 2, 7, 0 9, 8, 7, 0, 4, 8, 4, 4, 4, 3 5, 7, 7, 2, 7, 6, 8, 0, 9, 4 6, 5, 7, 5, 4, 0, 1, 9, 5, 2 3, 0, 4, 9, 1, 5, 4, 5, 8, 3 — gutenmorgenuhu, Nov 12 '14 at 07:43
Down votes are really uncalled for, the problem is not in the sorting algorithm — Pumpkin, Nov 12 '14 at 08:03

score 3 · Accepted Answer · edited May 23 '17 at 11:57

3

As far as I can tell there is nothing wrong with your merge sort algorithm, however there is a problem of expectations in the line

a = merge(left,right);

Following this line you expect to change the value of a of the previous recursive call, but by doing so you only change the value you refer to within the local scope.

I have tried to demonstrate the problem in the code below :

public static void main(String[] args)
{
    Integer[] arr = new Integer[1];
    arr[0] = 0;

    changeArray(arr);

    System.out.println(arr[0]);

    changeArrayCorrected(arr);

    System.out.println(arr[0]);
}

public static void changeArray(Integer[] arr)
{
    Integer[] anotherArray = new Integer[1];
    anotherArray[0] = 1;
    arr = anotherArray;
}

public static void changeArrayCorrected(Integer[] arr)
{
    arr[0] = 1;
}

You will see that output is 0 and 1 respectively, for the exact same reason.

More on the topic :

Are arrays passed by value or passed by reference in Java?

Exact solution :

Replace the line ->

a = merge(left,right);

With ->

System.arraycopy(merge(left,right),0, a, 0, a.length);

edited May 23 '17 at 11:57

Community

1
1

answered Nov 12 '14 at 08:01

Pumpkin

1,993
3
26
32

What that means is, that changeArray gets a copy of the reference-value from arr (lets call it arrCopy) but the reference arrCopy ------> (Memory) is swapped to arrCopy -------> (Memory of anotherArray); ? – gutenmorgenuhu Nov 12 '14 at 11:28
But I cannot see, why this affects my problem. a is the copy of the reference to my array (to be sorted). left and right are references to copies of the divided array. merge merges these arrays to a longer array and the reference a is assigned to this return value. I cannot see, why thats a problem – gutenmorgenuhu Nov 12 '14 at 11:48
I got a bit further @Pumpkin (I think) My merge code is correct. But the assignment a = merge(left,right) does only repoint the reference of my local a to a new memory location. But the array outside is not affected. But two things still give me headaches: 1. How do I achieve an effect on my array-to-be-sorted 2. Why are there about 55% correctly sorted arrays if my code does not work – gutenmorgenuhu Nov 12 '14 at 14:11
1

Try : System.arraycopy(merge(left,right),0, a, 0, a.length); instead of using "=" operator – Pumpkin Nov 12 '14 at 14:32
That was the solution. Thank you for the detailed explanation. I tried the same with Arrays.copyOf but that does not work, because it creates a new array. System.arraycopy does really copy the values into the memory the reference is pointing at.! – gutenmorgenuhu Nov 12 '14 at 15:52

MergeSort problems

1 Answers1