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

        mer开发者_如何转开发gesort(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?

Here's your original algorithm with some corrections and stylistic improvements:

public class MergeSort {  
    public static void main(String[]args) { 
        int[] nums = {12,9,4,99,120,1,3,10};
        mergeSort(nums);
        System.out.println(java.util.Arrays.toString(nums));
        // "[1, 3, 4, 9, 10, 12, 99, 120]"
    }
    static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
    }
    static void mergeSort(int[] arr, int low, int high, int[] buff){
        if (low >= high) {
            return;
        }
        int mid = (low + high) >>> 1;
        mergeSort(arr, low, mid, buff);
        mergeSort(arr, mid+1, high, buff);
        for (int left = low, right = mid + 1, i = low; i <= high; i++) {
            if (right > high || left <= mid && arr[left] <= arr[right]) {
                buff[i] = arr[left++];
            } else {
                buff[i] = arr[right++];
            }
        }
        for (int i = low; i <= high; i++) {
            arr[i] = buff[i];
        }
    }
}

Unlike Eyal's implementation, where the role of src and dst are swapped back and forth through the levels of recursion, here we always sort to the same array object arr, and the array object buff is always used only as a temporary buffer for merging (and consequently, there's a copy phase after the merge phase). This is still O(N log N), but Eyal's more advanced implementation will be a constant-factor improvement.

On the merge loop

Essentially you have a left index for the left subarray, and right index for the right subarray, and you pick the right element from either the left or right to put into buff.

The valid range of elements are (inclusive bounds):

• left = low...mid for left subarray
• right = mid+1...high for right subarray

To evaluate which element to pick, consider the condition under which the left element is picked. It happens when:

• There are no more element to pick from the right subarray (i.e. right > high)
• OR (conditionally) there's still an element to pick from the left subarray (i.e. left <= mid) and (conditionally) that element is less than or equal to the element from the right subarray (i.e. arr[left] <= arr[right]).

It's important to use short-circuiting conditional-and && (JLS 15.23) and conditional-or || (JLS 15.24) operators here, and to order these conditions accordingly. Otherwise you'll get an ArrayIndexOutOfBoundsException.

Related questions

• What’s the difference between | and || in Java?
• Shortcut “or-assignment” (|=) operator in Java Java
• Why doesn’t Java have compound assignment versions of the conditional-and and conditional-or operators? (&&=, ||=)

On finding average between two numbers

It's common to see the following:

int mid = (low + high) / 2; // BROKEN! Can result in negative!

The problem is that nowadays, arrays/lists etc can easily exceed 2³⁰ elements, and the above would cause an overflow and results in a negative number.

The new idiom, as advocated by Josh Bloch, is the following:

int mid = (low + high) >>> 1; // WORKS PERFECTLY!

This uses the unsigned right shift operator (JLS 15.19); it handles any overflow on the addition correctly for our need.

References

• Official Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken

Related questions

• Bitwise Operations — Arithmetic Operations
  • Explains how bitwise shifting relates to power-of-two arithmetics
• Java’s >> versus >>> Operator?
• Difference between >>> and >> operators
• Difference between >>> and >>

On array declarations

Do not make a habit of declaring arrays like this:

int x[];

You should instead put the brackets with the type, rather than with the identifier:

int[] x;

Related questions

• Is there any difference between Object[] x and Object x[] ?
• Difference between int[] myArray and int myArray[] in Java
• in array declaration int[] k,i and int k[],i
  • These declarations result in different types for i!

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.

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