合并排序算法不适用于大型数据集

Question

我正在研究合并排序算法，无法找到我的错误。输出基本上是排序的，直到最后它随机列出几个整数:

1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20 21日22日23日24日25日26日27 28 29日31日32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 93 95 96 97 98 99 100 83 13 14 94

public static void main(String args[]) throws IOException {

Scanner scan = new Scanner(System.in);
System.out.println("Enter dataset size: ");
int size = scan.nextInt();
String file = "" + size + ".txt";

scan.close();
Scanner scanner = new Scanner(new File(file));



// read numbers from text file into the array
// set array size to the user input size
// while loop reads text file until each int is read
int array[] = new int[size];
int i = 0;
while(scanner.hasNext()) {
array[i++] = scanner.nextInt();
}
scanner.close();




// create 4 copies of the array to test each in a separate algorithm
int array1[] = new int[size];
int array2[] = new int[size];
int array3[] = new int[size];
int array4[] = new int[size];
for (int j = 0; j < array.length; j++) {
array1[j] = array[j];
array2[j] = array[j];
array3[j] = array[j];
array4[j] = array[j];
}



// test bubble sort
// this inputs the array and outputs time taken to compute
bubbleSort(array1);

// test selection sort
// this inputs the array and outputs time taken to compute
selectionSort(array2);



//quickSort(array3, 0, array3[array3.length-1]);

// test merge sorting algorithm
mergeSort(array4, 0, array4[array4.length-1]);

System.out.println();
for (int k = 0; k<array4.length; k++) {
System.out.print(array4[k] + " ");
}


}
public static void mergeSort(int arr[], int start, int end) {
if (start < end) {
int mid = (start + end)/2;
mergeSort(arr, start, mid);
mergeSort(arr, mid+1, end);
merge(arr, start, mid, end);
}
}


private static void merge(int arr[], int start, int mid, int end) {
int n1 = mid - start + 1;
int n2 = end - mid;
int left[] = new int[n1];
int right[] = new int[n2];
for (int i = 0; i <n1; i++) {
left[i] = arr[start+i];
}
for (int j = 0; j < n2; j++) {
right[j] = arr[mid + 1 + j];
}

int i = 0; 
int j = 0; 
int k = start;

while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}

while (i < n1) {
arr[k] = left[i];
i++;
k++;
}

while (j < n2) {
arr[k] = right[j];
j++;
k++;
}
}

Answer 1

问题在于你如何称呼你的mergeSort:

// test merge sorting algorithm
mergeSort(array4, 0, array4[array4.length-1]);

试着用array4.length-1代替array4[array4.length-1]。