extra storage merge sort

Question

I need make a merge sort using an additional array. Here is my code:

public class extra_storage{  
    public static void main(String[]args) { 

        int x[]=new int[]{12,9,4,99,120,1,3,10};
        int a[]=new int[x.length];

        mergesort(x,0,x.length-1,a);
        for (int i=0;i<x.length;i++){
            System.out.println(x[i]);
        }       
    }

    public static void mergesort(int x[],int low,int high, int a[]){      
        if (low>=high) {
            return;
        }
        int middle=(low+high)/2;
        mergesort(x,low,middle,a);
        mergesort(x,middle+1,high,a);
        int k;
        int lo=low;
        int h=high;
        for (k=low;k<high;k++)
            if ((lo<=middle ) && ((h>high)||(x[lo]<x[h]))){
                a[k]=x[lo++];
            }
            else {
                a[k]=x[h++];
            }
        for (k=low;k<=high;k++){
            x[k]=a[k];
        }     
    }
}

But something is wrong. When I run it the output is this:

1
0
3
0
4
0
9
0

What is the problem?

Answer 1

You appear to have a stack overflow.

In your code

public static void mergesort(int x[],int low,int high, int a[]){      
    if (low>high) {
        return;
    }
    int middle=(low+high)/2;
    mergesort(x,low,middle,a);
    mergesort(x,middle+1,high,a);

If low starts off lower or equal to high, then it will end up equal to high, in which case middle==low==high and it will call itself forever.

---

Question was changed to remove stack overflow after answer submitted.

Answer 2

Your code is not clear enough, and it has many irrelevant operations. Furthermore, it doesn't exhibit the behavior you describe.

The idea of the mergesort version you are trying to implement is to use a single auxiliary array (source array) of the same size as the input array (destination array). This allows merging from one array into the other, since there is no efficient in-place merging technique. The algorithm consists of sorting the two halves of the destination array into the corresponding ranges in the source array, and then merging back the two halves into the destination array. Note that this requires that in every invocation the two arrays are identical in the range specified by low and high.

Following is such an implementation for int arrays. You can add optimizations like doing insertion sorts for small inputs, or appending halves instead of merging them when possible. This kind of optimizations can be found in the implementation of Arrays.sort(Object[]).

public static void mergeSort(int[] arr){
    int[] aux = arr.clone();
    mergeSort(aux, 0, arr.length, arr);
}

private static void mergeSort(int[] src, int low,  int high, int[] dst) {
    // One or no items - nothing to sort  
    if (high-low<=1)
        return;

    // Recursively sorting into src
    int mid = (low + high) / 2;
    mergeSort(dst, low, mid, src);
    mergeSort(dst, mid, high, src);

    // Merge halves into dst
    for(int i = low, p = low, q = mid; i < high; i++) {
        if (q >= high || p < mid && src[p] <= src[q])
            dst[i] = src[p++];
        else
            dst[i] = src[q++];
    }
}