# merge sort

MERGE(A, p, q, r)
1  n1 ← q – p + 1//修改为 n1 ← q – p
2  n2 ← r – q    //修改 n2 ← r – q + 1
3  create arrays L[1 ‥ n1 + 1] and R[1 ‥ n2 + 1]
4  for i ← 1 to n1
5       do L[i] ← A[p + i – 1]
6  for j ← 1 to n2
7       do R[j] ← A[q + j]
8  L[n1 + 1] ← ∞
9  R[n2 + 1] ← ∞
10  i ← 1
11  j ← 1
12  for k ← p to r
13       do if L[i] ≤ R[j]
14             then A[k] ← L[i]
15                  i ← i + 1
16             else A[k] ← R[j]
17                  j ← j + 1MERGE-SORT(A, p, r)
1 if p < r
2   then q ← (p + r)/2
3        MERGE-SORT(A, p, q)
4        MERGE-SORT(A, q + 1, r)
5        MERGE(A, p, q , r)//修改为MERGE(A, p, q + 1, r)

public class MergeSortAlgorithm {
final static int MAXVALUE = 10000;
static int[] L;
static int[] R;
public static void Merge(int[] A, int p, int q, int r) {
int n1 = q – p; //correct
int n2 = r – q + 1; //correct
//int n1 = q-p;
// int n2 = r – q;
L = new int[n1 + 1];
R = new int[n2 + 1];
for (int i = 0; i < n1; i++) {
L[i] = A[p + i];
}
for (int j = 0; j < n2; j++) {
R[j] = A[q + j];
}
L[n1] = MAXVALUE;
R[n2] = MAXVALUE;
int i = 0, j = 0;
for (int k = p; k <= r; k++) {
//for(int k = p; k < r ;k++)
{
if (L[i] <= R[j]) {
A[k] = L[i];
i++;
} else {
A[k] = R[j];
j++;
}
}
}
}
public static void MergeSort(int[] A, int p, int r) {
int q;
if (p < r) {
q = (p + r) / 2;
/*correctness*/
MergeSort(A, p, q);
MergeSort(A, q + 1, r);
Merge(A, p, q + 1, r);
/*test*/
/*
MergeSort(A,p,q);
MergeSort(A,q,r);
Merge(A,p,q,r);*/
}
}
public static void main(String[] args) {
int[] inputArray = {1, 3, 2, 6, 5, 2, 4, 7, 1, 3, 2, 6, 5, 2, 4, 7,
1, 3, 2, 6, 5, 2, 4, 7, 1, 3};
MergeSort(inputArray, 0, inputArray.length – 1);
for (int i = 0; i < inputArray.length; i++) {
System.out.println(“intArray[” + i + “]=” + inputArray[i]);
}
}
}