一：概念

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的

二：递归实现

具体代码实现：
process()函数就是每次都把序列分成两部分，这样无限细分下去；
merge()函数就是精髓所在，对每一个分出的序列进行排序；

    // 递归方法实现
	public static void mergeSort1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process(arr, 0, arr.length - 1);
	}

    public static void process(int[] arr, int L, int R) {
		if (L == R) { 
			return;
		}
		int mid = L + ((R - L) >> 1);
		process(arr, L, mid);
		process(arr, mid + 1, R);
		merge(arr, L, mid, R);
	}

	public static void merge(int[] arr, int L, int M, int R) {
		int[] help = new int[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		while (p1 <= M && p2 <= R) {
			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
		}
		// 要么p1越界了，要么p2越界了
		while (p1 <= M) {
			help[i++] = arr[p1++];
		}
		while (p2 <= R) {
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
	}

三：非递归实现

1.执行流程
原始序列:49 38 65 97 76 13 27

1）将原始序列看成7个只含有一个关键字的子序列，显然这些子序列都是有序的。
子序列1: 49
子序列2: 38
子序列3: 65
子序列4: 97
子序列5: 76
子序列6: 13
子序列7: 27

2）两两归并，形成若干有序二元组，即49和38归并成{38 49}，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象，保持原样。第一趟归并排序结束，结果如下:
{38 49}，{65 97}，{13 76}，{27}

3）再将这个序列看成若干二元组子序列
子序列 1：38 49
子序列 2：65 97
子序列 3：13 76
子序列 4：27
最后一个子序列长度可能是1，也可能是2。

4）继续两两归并，形成若干有序四元组(同样，最后的子序列中不一定有4个关键字)，即{38 49}和{65 97}归并形成{38 49 65 97}，{13 76}和{27}归并形成{13 27 76}。第二趟归并排序结束,结果如下:
{38 49 65 97}，{13 27 76}

5）最后只有两个子序列了，再进行一次归并，就可完成整个归并排序，结果如下:
13 27 38 49 65 76 97

由以上分析可知，归并排序可以看作一个分而治之的过程（关于分治法，可以看本书最后一章的讲解):先将整个序列分为两半，对每一半分别进行归并排序，将得到两个有序序列，然后将这两个序列归并成一个序列即可。

具体代码实现：

    // 非递归方法实现
	public static void mergeSort2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int N = arr.length;
		// 步长
		int mergeSize = 1;
		while (mergeSize < N) { // log N
			// 当前左组的，第一个位置
			int L = 0;
			while (L < N) {
				if (mergeSize >= N - L) {
					break;
				}
				int M = L + mergeSize - 1;
				int R = M + Math.min(mergeSize, N - M - 1);
				merge(arr, L, M, R);
				L = R + 1;
			}
			// 防止溢出
			if (mergeSize > N / 2) {
				break;
			}
			mergeSize <<= 1;
		}
	}

引：2019年408中数据结构一道考察快速排序的选择题

答案：D

定位：这道题在考察快速排序中一趟的概念。注意，基本的冒泡，插入，选择排序的一趟概念很容易理解，

接下来我们要讨论的是递归排序算法中（本文以快排和归并排序）讨论“趟”是否有意义。（先说结论，有，但并不像基本排序算法里那么简单，或者说，像基本算法里那么有普适性，归并排序只有非递归实现才有讨论趟的必要性，而快速排序更为复杂一些）

思路：

回想教材（《数据结构》严）里对一趟的定义

算法描述：

可见第一张图的过程实际上是递归形式实现的快排第一次调用Partition函数产生的结果。

然而，我们知道，如果第一次选中的pivot处在了待排序元素最终结果中的中间位置。那么接下来的处理也是递归进行的，

如图(a)所示，在第一次调用Patition函数后，元素49被放到了最终位置，之后对49左侧位置元素调用Qsort进行处理，

之后，关键关键的一步来了。

对 49左侧位置元素（27 48 13）调用Qsort处理时，首先调用Partition函数选出Pivot 27（默认第一个元素作pivot），

接下来呢？是立刻返回并去处理49右边的元素再调用一次Partition吗？并不是，这显然不是递归函数执行过程，

正确的执行过程是在对（27 48 13）这个左子表调用Partition后变为（13 27 48）接下来会继续对27左侧子表调用Qsort进行处理。

什么意思？等递归函数处理到 49右侧位置元素 时，其左侧元素都已经排好序了！

我们再看题干描述 趟 的概念：对尚未确定最终位置的所有元素进行一遍处理称为一趟。

发现问题了吗？如果是递归实现的快排，按题干的的意思，把所有尚未确定最终位置元素进行一遍处理，只有第一次选中的元素处在最终位置的边缘，

才能保证有第二趟的概念，为什么？很简单，如果第一次选中的元素恰好在最终位置中间部分，比如教材里这个例子，那么严格意义上讲，这种情况下它的执行过程只有两趟（递归实现的快排）！

最新更改：上面我的结论有问题，如果第一次pivot选在了中间，也是有第二趟概念的。以2019年408选择题为例：
D选项中12和32排在了最终位置，那么假设这是两趟的结果吧，那得满足什么条件？
或者说D选项怎么改才算正确？
答：2，5，12，28，16，32，72，60（只是其中一种可能）
没错，把12左侧元素改为顺序即为可能出现的情况，也就是对应的快排代码中递归的顺序是先对pivot左侧递归调用Qsort，左侧都已经有序了，
再对右侧进行一次递归调用Qsort，首先会调用Partition，那么刚进行完这次Partition后，得到的结果即为“第二趟”。

注意这里的 趟 是题目定义的趟，对所有的未确定最终位置元素进行一遍处理。

（这里注意区分，我们平时讲的快速排序最坏情况下（初始情况完全有序），它的递归次数会达到最高（不是这里题目中的趟数））

简单反思下这个题纠结在哪了？快速排序我们平时记得多是Partition函数会使待排序数列产生一个位于最终位置的元素。

平时的教材中多是这样描述

就容易先入为主地认为1之后立刻执行2或者1，2同时进行（实际上的确有并行快速排序算法），

然而我们熟悉的多是递归形式实现的快速排序算法，PS：我又去查了下非递归实现的快排，多是用栈模拟..（把栈模拟出来，这难道就不算递归吗？）

这时另外一些稀奇古怪的问题冒出来了：所有的递归都可以改成非递归吗？手动压栈这种写法就不算递归了吗？（深坑，暂时不多做探讨，之所以会有这个问题是因为我看到了递归和非递归归并算法的实现）

即同样的，也有类似问题，问归并排序的“第二趟”处理结果类似问题

对序列25，57，48，37，12，82，75，29进行二路归并排序，第二趟归并后的结果为（）。
A．25，57，37，48，12，82，29，75
B．25，37，48，57，12，29，75，82
C．12，25，29，37，48，57，75，82
D．25，57，48，37，12，82，75，29

然而，我们平时写的也多是递归形式的，

//递归形式
void Msort(int a[], int l, int r)
{
    mid = (l + r) / 2
	Msort(a,l,mid);
	Msort(a,mid+1,r);
	merge(a,l,r,mid);	//合并两个子表
}

还是和快排相似的问题：递归形式的归并排序有“趟”的概念吗？（如果按照和上一道题定义的趟的概念，是没有的！没有！）

那题就错了吗？不是，因为归并排序可以不借助栈，由循环结构实现。

非递归形式的归并排序思想是以2^k递增的间隔来划分待排序序列

void non_recur_msort(int arr[], int temp[], int left_end, int right_end)
{

 for(int i = left_end; i <= right_end; i = 2*i)
 {//i 是划分长度，以2^k速度递增,
  for(int j = left_end; j <= right_end-i; j += 2*i)
    //j用来迭代处理每个划分长度下，待排序序列划分得到的子表
    merge(arr, temp, j, j+i-1, Min(j + 2*i - 1 , right_end)); 
    //子表长度为i，合并的两个子表左子表起始位置为j，mid为 j+i-1，右子表终止位置为j+2*i-1，
 }
}

有些人会纠结奇数个元素怎么被处理的，看两张图，第一张是递归归并排序过程，第二张是非递归归并排序过程

第一张图——递归实现的归并排序是自顶向下划分（也就是划分时由大到小，再把小规模逐步求解），之后自底向上合并。

第二张图——非递归实现的归并排序的划分是由小到大（注意对比着上一张图看）

写到这，又回到了之前问题，快速排序的非递归形式会不会有类似（归并排序非递归方式）的实现？

似乎好多所谓的非递归只是手动实现了栈操作，然而我不确定这算不算是非递归。还有需要想到的应该是有没有并行快速排序的实现？

因为如果是并行实现的快排，那么同时调用Partition函数也就可以解释了

反思总结

像一些最基本的排序如插入排序，冒泡排序，选择排序的实现。在讨论一趟概念的时候并不需要考虑这么多。Why？

因为这些最基本的算法思想是迭代，什么是迭代？是逐步求得结果并更新，和一趟的概念较契合：每迭代处理一次所有未排序元素，就会求解出一个未排序元素最终位置。

而快排和归并接触到的写法多是递归形式的，利用了分治的思想，既然涉及分治，就无法避免划分和求解问题的顺序问题。

出现这个问题的根源是我们用递归方式去思考问题划分问题时是正向进行的，而实际运算处理是自底向上（递归划分到最底层再向上求解）的，这一点很容易混淆。

那说了半天遇到这种问题怎么搞？

如果是快速排序问第二趟，那么只有第一趟选中的元素位于边缘，才能有第二趟的存在，第k趟以此类推，或者换句话说，快速排序如果运行产生了第2，3，4，5趟，那一定是出现了初始状态导致了最坏情况的问题（也就是初始状态基本有序，导致递归趟数最大），这种情况下，递归趟数和排序趟数是一样的。

如果是归并排序第二趟，那么默认是在讨论非递归形式的归并排序（注意不是把栈写出来就算了..从本质上讲你把栈写出来并不能算是把递归算法转化成了非递归算法）

总而言之，趟是个非常鸡肋的概念，国外教材中暂时没有见过类似于趟描述，进一步说，这个概念纯粹是造出来出题玩的，无聊至极

后记：

去stackoverflow上找了下non-recursion quicksort without a stack，没想到用英文搜问题抓到了我疑惑的实质：

非尾递归的递归转化成iterative（迭代）算法是有代价的，那就是格外的数据结构（栈），原理涉及计算理论里图灵完备性（然而我仍然纠结non-recursive这个概念，不过这玩意用了这么久总不可能所有人都错了吧..基本现在一提非递归就都在说用栈模拟...

StackOverflow上有一个人回复类似问题的角度值得记下来：

因为快速排序的思想是divide and conquer，因此在你不需要用到其他partition时候，必然需要额外的数据结构保存那些partition，因此是无法通过不添加额外数据结构来实现快速排序的

排序算法-归并排序

算法思想

归并：将两个或者两个以上的有序表组合成一个新的有序表的过程。假定待排序表中含有n个记录，则可以看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到$\lceil n/2\rceil$个长度为2或1的有序表；再两两归并，如此一直重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。

2路归并排序的过程如下图所示。

从归并的过程不难看出，其代码实现可以基于分治思想递归实现。其基本问题是如何实现两个有序序列的归并操作，该操作可以通过使用辅助数组以及双指针的方式实现。

合并两个有序数组的代码：
其中nums为待排序序列，temp为辅助数组，其长度与nums一致，low为要合并的左子序列的起点，mid为要合并的右子序列的起点。

public static void Merge(int[] nums,int[] temp, int low,int mid, int high){
        // 表的两段nums[low...mid]与nums[mid+1...high]都有序，将两段进行有序归并
        for(int i=low;i<=high;++i)  // 将nums[low...high]元素复制到temp中，防止之后修改nums产生错误
            temp[i] = nums[i];
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
            if(temp[i]<temp[j])    //比较nums中的low和mid+1为起点的子序列元素
                nums[k] = temp[i++];  //将较小值复制到nums中，使得归并后的序列有序
            else{
                nums[k] = temp[j++];
            }
        }
        while(i<mid+1) nums[k++] = temp[i++];  // 若左表未遍历完，将左表剩余元素复制到nums剩余位置
        while(j<=high) nums[k++] = temp[j++];  // 若右表未遍历完，将右表剩余元素复制到nums剩余位置
        // 以上while循环只有一最终会满足条件
    }

Merge()的功能是将前后相邻的两个有序表归并为一个有序表的算法。设两段有序表$nums[low...mid]$和$nums[mid+\mathrm{1...}high]$存放在同一顺序表中相邻的位置上，先将它们复制到辅助数组temp中。每次从对应temp中的两个段取出一个记录进行关键字比较，将较小者放入nums中，当数组temp中有一段的下标超出其对应的表长时（即该段的所有元素已经完全复制到nums中），将另一段的剩余部分直接复制到nums中。

归并排序

分解：将含有n个元素的待排序表分成各含n/2个元素的子表，采用2-路归并排序算法对两个子表递归地进行排序；
合并：合并两个已排序的子表得到排序结果。

完整代码：

package com.sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] nums = {3,8,4,5,6,8,9,0,1};
        int[] temp = new int[nums.length]; //创建辅助数组，方便之后进行有序序列归并
        mergesort(nums,temp,0,nums.length-1);
        for(int num:nums){
            System.out.print(num+" ");
        }
    }
    public static void mergesort(int[] nums,int[] temps,int low,int high){
        if(low<high){
            int mid = (low + high) /2;  // 从中间划分两个西序列
            mergesort(nums,temps,low,mid);  // 对左侧子序列进行递归排序
            mergesort(nums,temps,mid+1,high);  // 对右侧子序列进行递归排序
            Merge(nums,temps,low,mid,high);   //合并左右有序子序列
        }
    }
    public static void Merge(int[] nums,int[] temp, int low,int mid, int high){
        // 表的两段nums[low...mid]与nums[mid+1...high]都有序，将两段进行有序归并
        for(int i=low;i<=high;++i)  // 将nums[low...high]元素复制到temp中，防止之后修改nums产生错误
            temp[i] = nums[i];
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<mid+1 && j<=high;++k){
            if(temp[i]<temp[j])    //比较nums中的low和mid+1为起点的子序列元素
                nums[k] = temp[i++];  //将较小值复制到nums中，使得归并后的序列有序
            else{
                nums[k] = temp[j++];
            }
        }
        while(i<mid+1) nums[k++] = temp[i++];  // 若左表未遍历完，将左表剩余元素复制到nums剩余位置
        while(j<=high) nums[k++] = temp[j++];  // 若右表未遍历完，将右表剩余元素复制到nums剩余位置
        // 以上while循环只有一最终会满足条件
    }

}

复杂度分析

从2路归并排序的过程图中，易知2路归并的归并树形态就是一棵“倒立”的二叉树。

时间复杂度：
如果“归并树”树高为h，则归并排序所需要的归并趟数为h-1趟。二叉树的第h层最多有$2^{h-1}$个结点。若树高高为h，则应满足n<=$2^{h-1}$，因为树的第h层必然包含n个结点，即可得$h-1=\lceil lo{g}_{2}n\rceil$。又因为对n个元素进行归并排序，归并总趟数为h-1，即n个元素进行二路归并，归并趟数为$\lceil lo{g}_{2}n\rceil$。

每一趟的归并的时间复杂度，即Merge()的时间复杂度为$O(n)$，所以归并排序的时间复杂度就为 归并的时间复杂度 * 归并的趟数，即时间复杂度为$O(nlo{g}_{2}n)$。无论序列有序、无序，其时间复杂度都为$O(nlo{g}_{2}n)$。

空间复杂度：
辅助数组需要n个存储单元，空间复杂度为$O(n)$。
递归的深度为数的高度，空间复杂度为$O(lo{g}_{2}n)$。
整体来看，归并排序空间复杂度为$O(n)$。

稳定性：稳定。