归并排序

归并排序采用的是分治(divide-and-conquer)法思想。

1.基本思想：
将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

2.执行过程：

3.时间复杂度
　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
　
4.空间复杂度
　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

5.代码：

package sort;public class MergeSort {public static void merSort(int[] arr,int left,int right){if(left < right){int mid = (left+right)/2;merSort(arr,left,mid);//左边归并排序merSort(arr,mid+1,right);//右边归并排序merge(arr,left,mid,right);//合并两个子序列}}private static void merge(int[] arr,int left,int mid,int right){int[] temp = new int[right - left + 1];//申请一个新的数组用来存储int i = left;int j = mid + 1;int k = 0;while(i <= mid && j <= right){if(arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while(i <= mid){temp[k++] = arr[i++];//左边剩余填充进temp中}while(j <= right){temp[k++] = arr[j++];//右边剩余填充进temp中}//将temp中的元素全部拷贝到原数组中for(int k2 = left;k2 < temp.length;k2++){arr[k2] = temp[k2];}}public static void main(String[] args) {int[] test = {9,2,6,3,5,7,10,11,12};merSort(test,0,test.length-1);for(int i = 0;i < test.length;i++){System.out.print(test[i] + " ");}}
}

一定要注意：

while(i <= mid){temp[k++] = arr[i++];//左边剩余填充进temp中}while(j <= right){temp[k++] = arr[j++];//右边剩余填充进temp中}

是小于等于

6.稳定性
　归并排序是一种稳定的排序