分(divide)的阶段：分成一些小的问题然后递归求解，时间复杂度为O(log2n)
治(conquer)的阶段：则将分的阶段得到的各答案"合并"在一起,时间复杂度为cn)
总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
递归
* long f(int n){
* if(n=1){
* return 1;
* }
* return n+f(n-1);
* }
第一版，merge方法中把定义了两个临时数组来进行合并
public class MergeSort {
public static void main(String[] args) {
//{1, 7, 5,3, 8 ,2, 4,6, 9};
int arr[] = {7, 1, 5,3};
int left = 0;
int right = 3;
sort(arr, left, right);
System.out.println("===============");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void sort(int arr[], int left, int right) {
if (right == left) {
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid + 1, right);
}
public static void merge(int arr[], int left, int mid, int right) {
int leftSize = mid - left;
int rightSize = right - mid + 1;
int leftArr[] = new int[leftSize];
int rightArr[] = new int[rightSize];
for (int i = left; i < mid; i++) {
leftArr[i-left] = arr[i];
}
for (int i = mid; i < right+1; i++) {
rightArr[i - mid] = arr[i];
}
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArr[i] < rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < leftSize) {
arr[k++] = leftArr[i++];
}
while (j < rightSize) {
arr[k++] = rightArr[j++];
}
}
}
第二版，merge方法中把定义了一个临时数组，但需要回写原数组
public class MergeSort_V2 {
public static void main(String[] args) {
//{1, 7, 5,3, 8 ,2, 4,6, 9};
int arr[] = {1, 7, 5,3, 8 ,2, 4,6};
int left = 0;
int right = 7;
sort(arr, left, right);
System.out.println("===============");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void sort(int arr[], int left, int right) {
if (right == left) {
return;
}
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid + 1, right);
}
public static void merge(int arr[], int left, int mid, int right) {
int[] tmp=new int[right-left+1];
int i = left, j = mid, k = 0;
while (i 
