归并排序的原理及时间复杂度
归并排序的定义：
归并排序算法采用的是分治算法,即先把要排序的数组分成两个(或两个以上)有序表，然后再合并成一个新的有序表,即把待排序的序列分成若干个子序列,每个子序列都是有序的,然后把有序子序列合并成整体有序序列,这个过程也称为2-路归并.注意:归并排序的一种稳定排序,即相等元素的顺序不会改变.归并排序的原理
将待排序的数组分成前后两个部分，再递归的将前半部分数据和后半部分的数据各自归并排序，得到的两部分数据，然后使用merge合并算法（算法见代码）将两部分算法合并到一起。
例如：如果N=1；那么只有一个数据要排序，N=2，只需要调用merge函数将前后合并，N=4，……….. 也就是将一个很多数据的数组分成前后两部分，然后不断递归归并排序，再合并，最后返回有序的数组。归并排序的时间复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。代码：
public class MergeSort {
private static void mergeSort(int[] array,int[] tmp,int left,int right){
if(left<right){
int center = ( left + right ) / 2;//取数组的中点
mergeSort(array,tmp,left,center);//归并排序数组的前半部分
mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
}
}
/*
* 超简单的合并函数
*/
private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
// TODO Auto-generated method stub
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(array[leftPos]<=array[rightPos]){
tmp[tmpPos++] = array[leftPos++];
}else{
tmp[tmpPos++] = array[rightPos++];
}
}
while(leftPos <= leftEnd){
tmp[tmpPos++] = array[leftPos++];
}
while(rightPos <= rightEnd){
tmp[tmpPos++] = array[rightPos++];
}
for(int i=0;i<numElements;i++,rightEnd--){
array[rightEnd] = tmp[rightEnd];
}
}
public static void mergeSort(int[] array){
int[] tmp = new int[array.length];//声明一个用来合并的数组
mergeSort(array,tmp,0,array.length-1);//调用排序函数，传入数字的起点和终点
}
}