extra storage merge sort
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?
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.
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:
right > high ) left <= mid ) and (conditionally) that element is less than or equal to the element from the right subarray (ie 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
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 230 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
Related questions
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
Object[] x and Object x[] ? int[] myArray and int myArray[] in Java int[] k,i and int k[],i i ! 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++];
}
}
上一篇: 如何在java中从头开始创建addAll（）或addRange（）方法？
下一篇: 额外的存储合并排序