将n个元素的数据序列看成是由n个长度为1的排序子序列组成，反复将相邻的两个子序列归并成一个排序子序列，直到合并成一个序列，则排序完成。
package top.einino.mergesort;
public class MergeSort {
//将X中分别以begin1, begin2开始的两个相邻子序列归并（升序）到Y中， 子序列长度为n private static void merge(int[] X, int[] Y, int begin1, int begin2, int n){ int i = begin1, j = begin2, k = begin1; //将X中两个相邻子序列归并到Y中 while(i<begin1+n && j<begin2+n && j<X.length){ //升序将较小值复制到Y中 if(X[i]<X[j]){ Y[k++] = X[i++]; }else{ Y[k++] = X[j++]; } } //将前一个子序列剩余元素复制到Y，序列长度可能不足n while(i<begin1+n && i<X.length){ Y[k++] = X[i++]; } //将后一个子序列剩余元素复制到Y中 while(j<begin2+n && j<X.length){ Y[k++] = X[j++]; } } //一趟归并，将X中若干相邻子序列两两归并到Y中，子序列长度为n private static void mergepass(int[] X, int[] Y, int n){ System.out.println("子序列长度n="+ n + " "); for(int i=0; i<X.length; i+=2*n){ merge(X, Y, i, i+n, n); } print(Y); } //归并排序（升序） private static void mergeSort(int[] X){ //Y数组长度同X数组 int[] Y = new int[X.length]; //排序子序列长度，初值为1 int n = 1; while(n<X.length){ //一趟归并，将X中若干邻子序列归并到Y mergepass(X, Y, n); //子序列长度加倍 n*=2; if(n<X.length){ //一趟归并，将Y中若干相邻子序列再归并到X mergepass(Y, X, n); n*=2; } } } //输出排序数组 private static void print(int[] keys) { for(int key : keys){ System.out.print(key+" "); } System.out.println(); } public static void main(String[] args) { int[] X = {97, 82, 75, 53, 17, 61, 70, 12, 61, 58, 26}; mergeSort(X); } }
老师又来排队了！
初始队列：A学生197，B学生182，C学生175，D学生153，E学生117，F学生161，G学生170，H学生112，I学生161，J学生158，K学生126
老师开始第一趟排序
首先老师对所有学生进行相邻距离为1的学生分为一组，并且比较的是每组的前1位与后1位进行比较，分组情况如下：
第一组：A、B
第二组：C、D
第三组：E、F
第四组：G、H
第五组：I、J
第六组：K
进行第一组的排序，结果A>B、所以先将B拉出队伍排到第一位，再将剩下不用再进行排序的A拉出队伍排到B后面
进行第二组的排序，结果C>D，所以先将D拉出队伍排到A学生的后面，再将C学生排到D学生的后面
同理，对其他组进行排序：最后结果为
B学生182，A学生197，D学生153，C学生175，E学生117，F学生161，H学生112，G学生170，J学生158，I学生161，K学生126
老师进行第二趟排序，将上一趟排序的结果再进行分组相邻距离为2的分为一组，并且比较的是每组的前2位与后两位进行比较，分组情况如下：
第一组：B、A \ D、C
第二组：E、F \ H、G
第三组：J、I \ K
老师开始进行第一组排序，
首先进行B与D的比较，结果D<B，所以先将D学生拉出队伍，排到第一位，再将C与B进行比较，结果C<B,再把C拉出队伍，排到D的后面，然后依次把B、A排到C的后面
再进行第二组的排序
首先进行E与H的比较，结果E>H，所以行将H排到A学生的后面，再进行E与G的比较，结果E<G,再把E排到H的后面，再将F与G进行比较,结果F<G,所以把F排到E的后面，G依次排到F的后面
同理进行第三组的排序，结果为K、J、I
第二趟 排序的最后结果是D学生153，C学生175，B学生182，A学生197，H学生112，E学生117，F学生161，G学生170，K学生126，J学生158，I学生161
老师进行第三趟的排序
首先进行分组，以相邻距离为4的分为一组，并且比较的是每组前4位与后4位的比较，分组情况如下：
第一组：D、C、B、A\H、E、F、G
第二组：K、J、I
进行第一组的排序，
进行D与H的比较，结果D>H，所以先将H拉出队伍排到第一个，再进行D与E的比较，结果D>E，将E排到H的后面，再进行D与F的比较，结果D<F，所以将D排到E的后面，再进行F与C的比较，结果F<C，所以把F排到D的后面，再进行C与G的比较，结果C>G，所以将G排到F的后面，因为没得进行比较了，所以依次把C、B、A排到G的后面
再进行第二组的排序，因为第一组只有3个人，还不到4个人，就无需进行比较了
所以第三趟排序结果为：H学生112，E学生117，D学生153，F学生161，G学生170，C学生175，B学生182，A学生197，K学生126，J学生158，I学生161
老师进行第四趟的排序
首先进行分组，以相邻距离为8的分为一组，并且比较的是每组前8位与后8位的比较，分组情况如下：
第一组：H、E、D、F、G、C、B、A\K、J、I
老师进行第一组的排序，也是唯一一组，首先进行H与K的比较，结果H<K,所以先把H拉出队伍，排到第一位，再进行E与K的比较，结果E<K，把E排到H的后面，再进行D与K的比较，结果D>K,所以把K排到E的后面，再进行D与J的比较，结果D<J,所以把D排到K的后面，再进行比较F与J，结果F>J,所以把J排到D的后面，再进行F与I的比较，结果F=I，所以把F排到J的后面，再进行I与G的比较，结果G>I，所以把I排到F的后面，然后因为没得比较，所以依次把G、C、B、A排到I的后面，
最后的排序结果为：H学生112，E学生117，K学生126，D学生153，J学生158，F学生161，I学生161，G学生170，C学生175，B学生182，A学生197，
n个元素归并排序，每趟比较n-1次，数据移动n-1次，进行log2(n)趟，时间复杂度为O(n*log2(n))
归并排序需要O(n)容量的附加空间，与数据序列的存储容量相等，空间复杂度为O(n)
在归并排序算法中，关键字相等的元素会相遇进行比较，算法不改变它们的原有次序，所以，归并排序算法是稳定的
本博文从归并排序算法分析，升序代码实现，老师排队的例子讲演，时间复杂度，空间复杂度以及稳定性介绍了归并排序的方方面面。
如果有疑问或者对该博文有何看法或建议或有问题的，欢迎评论，恳请指正！
