代码如下：
创新互联是少有的成都网站设计、网站制作、外贸营销网站建设、营销型企业网站、微信小程序、手机APP,开发、制作、设计、外链、推广优化一站式服务网络公司,2013年开创至今,坚持透明化,价格低,无套路经营理念。让网页惊喜每一位访客多年来深受用户好评
private void merge(int[] array, int left, int mid, int right) {
int i = left;
int j = mid;
int length = right - left;
int[] extra = new int[length];
int k = 0;
while(i < mid && j < right) {
if(array[i] <= array[j]) {
extra[k++] = array[i++];
} else {
extra[k++] = array[j++];
}
}
while (i < mid) {
extra[k++] = array[i++];
}
while (j < right) {
extra[k++] = array[j++];
}
// 从 extra 搬移回 array
for (int t = 0; t < length; t++) {
// 需要搬移回原位置，从 low 开始
array[left + t] = extra[t];
}
}递归实现操作：
public void mergeSort(int[] array) {
mergeSortInternal(array, 0, array.length);
}
private void mergeSortInternal(int[] array, int left, int right) {
if(left >= right - 1)
return;
int mid = (left + right) >>> 1;
mergeSortInternal(array, left, mid);
mergeSortInternal(array, mid, right);
merge(array, left, mid, right);
}public void mergeSort(int[] array) {
for (int i = 1; i < array.length; i = i * 2) {
for (int j = 0; j < array.length; j = j + 2 * i) {
int low = j;
int mid = j + i;
if (mid >= array.length) {
continue;
}
int high = mid + i;
if (high > array.length) {
high = array.length;
}
merge(array, low, mid, high);
}
}
}
