伪代码:
MERGE(A,p,q,r) n1 = q-p+1 n2 = r-q for i = 1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+i] L[1+n1]=无穷大 R[1+n2]=无穷大 i=1 j=1 for k = p to r if L[i]<=R[j] A[k] = L[i] i++ else A[k]=R[j] j++
Java代码实现:
private static void mergeSort(Integer[] r, int left, int right){ if(right<=left)//如果数组大小不大于1,不再递归 return; int mid = (left+right)/2; mergeSort(r, left, mid); mergeSort(r, mid+1, right); merge(r, left, mid, right); } private static void merge(Integer[] r, int left, int mid, int right){ int i=left, j=mid+1; for(int k=left; k<=right; k++) aux[k] = r[k]; for(int k=left; k<=right; k++) if(i>mid)//mid是左侧数列的最后一个位置。这里判断i是否溢出 r[k] = aux[j++]; else if(j>right) r[k] = aux[i++]; else if(aux[i]<aux[j])//比较元素的大小 r[k] = aux[i++]; else r[k] = aux[j++]; }