1、基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
2、实例
3、java实现
1 package com.sort; 2 3 //稳定 4 public class 归并排序 { 5 public static void main(String[] args) { 6 int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 7 System.out.println("排序之前："); 8 for (int i = 0; i < a.length; i++) { 9 System.out.print(a[i]+" "); 10 } 11 //归并排序 12 mergeSort(a,0,a.length-1); 13 System.out.println(); 14 System.out.println("排序之后："); 15 for (int i = 0; i < a.length; i++) { 16 System.out.print(a[i]+" "); 17 } 18 } 19 20 private static void mergeSort(int[] a, int left, int right) { 21 if(left<right){ 22 int middle = (left+right)/2; 23 //对左边进行递归 24 mergeSort(a, left, middle); 25 //对右边进行递归 26 mergeSort(a, middle+1, right); 27 //合并 28 merge(a,left,middle,right); 29 } 30 } 31 32 private static void merge(int[] a, int left, int middle, int right) { 33 int[] tmpArr = new int[a.length]; 34 int mid = middle+1; //右边的起始位置 35 int tmp = left; 36 int third = left; 37 while(left<=middle && mid<=right){ 38 //从两个数组中选取较小的数放入中间数组 39 if(a[left]<=a[mid]){ 40 tmpArr[third++] = a[left++]; 41 }else{ 42 tmpArr[third++] = a[mid++]; 43 } 44 } 45 //将剩余的部分放入中间数组 46 while(left<=middle){ 47 tmpArr[third++] = a[left++]; 48 } 49 while(mid<=right){ 50 tmpArr[third++] = a[mid++]; 51 } 52 //将中间数组复制回原数组 53 while(tmp<=right){ 54 a[tmp] = tmpArr[tmp++]; 55 } 56 } 57 }
4、分析
归并排序是稳定的排序方法。
归并排序的时间复杂度为O(nlogn)。
速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
五、基数排序