重写过程MERGE,使之不使用哨兵,而是一旦数组L或R的所有元素均被复制回A就立即停止,然后把另一个数组的剩余部分复制回A。
MERGE(A,p,q,r) n1 = q - p + 1 n2 = r - q let L[1..n1+1] and R[1..n2+1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = INT_MAX R[n2 + 1] = INT_MAX i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1