归并排序（Merge sort也译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
实现代码如下：
package com.teradata.lsw.sort;
import java.util.Arrays;
public class MergeSort {
/**
* 归并排序，从小到大 归并排序算法一般需要三步 1. 左边排序 2. 右边排序 3. 合并 需要用到递归调用
*
* @author TD_LSW
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 20, 34, 12, 23, 12, 56, 1, 28, 0, 2, 23, 56 };
MergeSort mergeSort = new MergeSort();
int[] result = mergeSort.mergeSort(a);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + ",");
}
System.out.println();
}
private int[] mergeSort(int[] a) {
// TODO Auto-generated method stub
if(a.length<2){
return a;
}
//获得分组中点
int mid = a.length%2==0 ? a.length/2:(a.length-1)/2;
//将数组a从mid处分成两个
int[] left = Arrays.copyOfRange(a,0, mid);
int[] right = Arrays.copyOfRange(a, mid, a.length);
//递归调用
int[] leftArray = mergeSort(left);
int[] rightArray = mergeSort(right);
return _mergeSort(leftArray,rightArray);
}
private int[] _mergeSort(int[] leftArray, int[] rightArray) {
// TODO Auto-generated method stub
int[] temp = new int[leftArray.length+rightArray.length];
int left =0;
int right = 0;
int m = 0;
while(left<leftArray.length&&right<rightArray.length){
if(leftArray[left]<rightArray[right]){
temp[m++] = leftArray[left++];
}else{
temp[m++] = rightArray[right++];
}
}
//若有数组还没比较完则把后面的直接插到temp的后面
while(left<leftArray.length){
temp[m++] = leftArray[left++];
}
while(right<rightArray.length){
temp[m++] = rightArray[right++];
}
return temp;
}
}
性能分析:
时间复杂度:
由于归并的趟数,等于树的高度Logn,每趟归并需要移动记录n次,因此归并排序的时间复杂度为nlogn.
空间复杂度:
从上面的算法可以看出,需要一个辅助空间num2,其长度等于n，所以归并排序的辅助空间为O(n).
稳定性:
归并排序不涉及到交换,因此它是一种稳定的排序算法。
归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越，但需要与序列等长的辅助空间。