总结
? ?
递归
从大到小进行排序
? ?
辅助数组，将两个子数组中最右边的两个数进行比较，大的放入辅助数组中，此时辅助数组的索引也从最右边开始
? ?
也可以从小到大进行排序，将两个子数组中最左边的两个数进行比较，小的放入辅助数组中，此时辅助数组的索引从最左边开始
? ?
剩下的就是合并两个排好序的子数组的代码
? ?
while (i >= start && j >= mid + 1) {
if (data[i] > data[j]) {
result[indexOfResult--] = data[i--];
} else {
result[indexOfResult--] = data[j--];
}
}
for (; i >= start; i--)
result[indexOfResult--] = data[i];
for (; j >= mid + 1; j--)
result[indexOfResult--] = data[j];
? ?
如果一个数组比较完了，那么把另外一个数组依次放入辅助数组中
? ?
package mergeSort;
? ?
public class MergeSort {
public static void main(String[] args) {
int[] data = { 1, 3, 5, 2, 4, 6 };
int[] result=data.clone();
mergeSort(data, result, 0, data.length-1);
for(int k:result) System.out.println(k);
}
? ?
static void mergeSort(int[] data, int[] result, int start, int end) {
if (start == end) {
result[start] = data[start];
return;
}
int mid = (start + end) / 2;
mergeSort(result, data, start, mid);
mergeSort(result, data, mid + 1, end);
? ?
int i = mid;
int j = end;
int indexOfResult = end;
while (i >= start && j >= mid + 1) {
if (data[i] > data[j]) {
result[indexOfResult--] = data[i--];
} else {
result[indexOfResult--] = data[j--];
}
}
for (; i >= start; i--)
result[indexOfResult--] = data[i];
for (; j >= mid + 1; j--)
result[indexOfResult--] = data[j];
}
}
原文：http://www.cnblogs.com/keedor/p/4360229.html