#include<stdlib.h>
#include<stdio.h>
/*
平均时间复杂度：O(nlog2n)
空间复杂度：O(n)  (用于存储有序子序列合并后有序序列)
稳定性：稳定
*/
 
void Merge(int source[],int temp[],int start,int mid,int end)
{
    int i = start;// i是第一段序列的下标
	int j= mid + 1;// j是第二段序列的下标
	int k = start;//k是临时的合并序列的下标

	// 扫描第一段和第二段序列，直到有一个扫描结束
    while(i!=mid+1 && j!=end+1)
    {// 判断第一段和第二段取出的数哪个更小，将其存入临时合并序列，并继续向下扫描
        if(source[i]<source[j])
            temp[k++] = source[i++];
        else
            temp[k++] = source[j++];
    }
    while(i!=mid+1)
        temp[k++] = source[i++];// 若第一段序列还没扫描完，将其全部复制到临时合并序列
    while(j!=end+1)
        temp[k++] = source[j++];// 若第二段序列还没扫描完，将其全部复制到临时合并序列
    for(i=start;i<=end;i++)//把temp数组中的结果装回source数组中
        source[i] = temp[i];
}
 
//内部使用递归
void MergeSort(int source[],int temp[],int start,int end)
{
    int mid;
	mid=(start+end)/2;
    if(start<end)
    {      
        MergeSort(source,temp,start,mid);//递归拆分左数组，直至数组元素个数为1
        MergeSort(source,temp,mid+1,end);//递归拆分右数组，直至数组元素个数为1
        Merge(source,temp,start,mid,end);//将左右两边有序的数组合并
    }
}
 
int main(int argc,char * argv[])
{
    int a[5]={8,7,6,5,4};
	int i,b[5] = {0};
    MergeSort(a,b,0,4);
    for(i=0;i<5;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

题目：如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1) ？ 
 思路分析： 
 （1）关键：哈希表，空间复杂度O(1)中1的含义（只要是常量就可以） 
 （2）在数字范围有限制的情况下，只需要用一个数组记录每个数字出现次数就可以了。 
 （3）假定你的数字范围在0到65535范围之内，定义一个数组count[65536]（这个空间是常量，和n无关，所以是O(1) )，初值全部为0。 
 假设待排序数组中有下面这些数字： 
 100，200，300，119，0，6… 
 那么对于每个数字，都做在count中记录一下： 
 100 => count[100]++ 
 200 => count[200]++ 
 300 => count[300]++ 
 119 => count[119]++ 
 0 => count[0]++ 
 6 => count[6]++ 
 … 
 最后，遍历一遍待排序数组中的所有数字，就可得到0~65535每个数字的个数（在count数组中），然后再顺序遍历count数组，count[n] = m，则输出m个n，（比如说有count[3] = 2, 那么说明有2个数字3），依次输出，最后可得结果。第一次遍历是O(n)，第二次遍历是O(1)，为常量，所以最后的时间复杂度为O(n)，而空间复杂度为O(1)。
 
具体实现如下：
 
#include <iostream>
using namespace std;
#define MAXSIZE 100

void hashSort(int arr[],int len)
{
    int max = arr[0];
    int min = arr[0];
    for (int i = 0; i < len; i++) // 找出待排序数组中的最大值和最小值
    {
        if(max <= arr[i])
            max = arr[i];
        if(min >= arr[i])
            min = arr[i];
    }

    int *hash = new int[max - min + 1]; // 根据最大值和最小值来动态创建一个新数组

    for (int i = 0; i < max - min + 1; i++) // 将新数组的元素全部初始化为0
        *(hash + i) = 0;

    for (int i = 0; i < len; i++) // 记录每个数出现的次数
        (*(hash+arr[i] - min))++;

    int j = 0;
    for (int i = 0; i < max - min + 1; i++)
    {
        while ((*(hash + i))--)// 出现k次，重复k次
            arr[j++] = i + min; // 新数组的每个下标位置存储的值，就是“该位置对应的下标的值”的“出现次数”。
    }
    delete [] hash;
}


int main(int argc, const char * argv[]) {

    int arr[] = {3,2,6,5,7,1,4,9,0,8};
    int len = sizeof(arr)/sizeof(int);

    hashSort(arr, len);

    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }

    printf("\n");
    return 0;
}
 
注意点： 
 int *hash = new int[max - min + 1]; 
 此处定义数组时，不能使用 int temp[max - min + 1];的形式，定义数组时不能用变量来指定数组长度，因为定义数组时，分配空间是需要一个固定的值，来确定你所申请的空间的大小。 
 如 int n = 5； 
 int a[n]; 
 这样使用，根据编译器的不同，编译可能会通过，但是那个n始终是个变量，若n的值改变，则数组大小也会改变，在对其使用的时候就会使用到数组以外的内容，对程序会造成隐患，所以一般是不能编译通过的。 
 所以，只能固定的申请a[5];即数组长度必须在编译时就已确定。 
 c++可以用new表达式动态分配数组和用delete [] 撤消，new表达式返回新分配数组的第一个元素的指针。 
 参考文章：【100题】第四十九题 排序，要求时间复杂度O(n)，空间复杂度O(1)

解析在下面
 
2-4，10,23题目写的有点问题，应该是104,105
 
 
 
 
 
 
 
 
解析：
 
p1-1：
 
注意哦，人家问的不是时间复杂度，而是归并趟数的数量级，应该是O(logN) 
 
x2-2：
 
空间复杂度就是O（N），因为需要开一个临时数组
 
x2-4：
 
就一位，个数也不多，直接桶排序最好，速度是线性的
 
x2-5：
 
用排除法很好做。。。至于为啥是快排我也不知道。。。
 
x2-6：

 对于10TB的海量数据，数据不可能一次全部载入内存，传统的排序方法就不适用了，需要用到外排序的方法。外排序采用分治思想，即先对数据分块，对块内数据进行排序，然后采用归并排序的思想进行排序，得到数据的一个有序序列。
 
 
x2-7：
 
归并一般用于外排序，如果用于内排，而不用插入 这种简单排序，
 
可能的原因也就只有c了。
 
a肯定错
 
b插入排序是不占空间的
 
x2-8：
 
这个很难
 
插入排序、选择排序、起泡排序原本时间复杂度是O(n2)，更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性（堆排序的这个特性体现在：取出最大堆的根节点后，更新堆的过程），而链式存储不支持这种性质，所以时间复杂度会增加，因此选D。
 
x2-9：
 
因为堆排序就是每次删除最大堆，并把它放在最后，其实这个过程有点像冒泡我觉得
 
x2-10：
 
同2-4:
 
x2-11，12,13：
 
第一步：以34为主元
 
第二部，左边递归排序
 
x2-15：
 
这个很明显就是插入排序的特点
 
x2-16：
 
这个题很好！！！
 
考查各排序算法的特点。
 解答本题要对不同排序算法的特点极为清楚。
 对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。
 （二路）归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。
 插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。故正确答案是B。
 
x2-17：
 
和上一题差不多，也可以用排除法分析，只能是快排
 
x2-19：
 
看表
 
 
x2-21：
 
归并排序用于都是O(NlogN)
 
x2-22：
 
看图
 
 
x2-23：
 
这个没有桶排序，但是只有一位，那就用它的升级版基数排序即可
 
后面的不用看了
 
 
 
 
 
 
 
 
 
 
 
 
 
1-1
 
对N个记录进行归并排序，归并趟数的数量级是O(NlogN)。 (2分)
 
T         F
 
2-1
 
对N个记录进行归并排序，归并趟数的数量级是： (1分)
 
O(logN)
O(N)
O(NlogN)
O(N​2​​)
作者: DS课程组
 
单位: 浙江大学
 
2-2
 
对N个记录进行归并排序，空间复杂度为： (1分)
 
O(logN)
O(N)
O(NlogN)
O(N​2​​)
作者: DS课程组
 
单位: 浙江大学
 
2-3
 
给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？ (2分)
 
→331→431→33→63→24→56→46→57→7→28
→56→28→431→331→33→24→46→57→63→7
→431→331→33→63→24→56→46→57→7→28
→57→46→28→7→33→24→63→56→431→331
作者: DS课程组
 
单位: 浙江大学
 
2-4
 
输入10​5​​个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是：(1分)
 
快速排序
插入排序
桶排序
希尔排序
作者: 陈越
 
单位: 浙江大学
 
2-5
 
数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果？(2分)
 
冒泡排序
快速排序
插入排序
堆排序
作者: 陈越
 
单位: 浙江大学
 
2-6
 
对10TB的数据文件进行排序，应使用的方法是：(1分)
 
希尔排序
堆排序
归并排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-7
 
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是：(2分)
 
归并排序的程序代码更短
归并排序占用的空间更少
归并排序的运行效率更高
仅 2
仅 3
仅 1、2
仅 1、3
作者: 考研试卷
 
单位: 浙江大学
 
2-8
 
下列排序方法中，若将顺序村吃更换为链式存储，则算法的时间效率会降低的是：(2分)
 
1.插入排序；2.选择排序；3.起泡排序；4.希尔排序；5.堆排序
 
仅1、2
仅2、3
仅3、4
仅4、5
作者: 考研试卷
 
单位: 浙江大学
 
2-9
 
{ 12，9，11，8，7，4，5，13，23 }是下列哪种方法第二趟排序后的结果？ (2分)
 
归并排序
堆排序
插入排序
基数排序
作者: DS课程组
 
单位: 浙江大学
 
2-10
 
输入10​4​​个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是：(1分)
 
桶排序
快速排序
插入排序
希尔排序
作者: 陈越
 
单位: 浙江大学
 
2-11
 
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
 
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
 
冒泡排序
快速排序
归并排序
插入排序
作者: 陈越
 
单位: 浙江大学
 
2-12
 
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
 
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
 
冒泡排序
归并排序
插入排序
快速排序
作者: 陈越
 
单位: 浙江大学
 
2-13
 
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
 
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
 
冒泡排序
归并排序
快速排序
插入排序
作者: 陈越
 
单位: 浙江大学
 
2-14
 
在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是： (1分)
 
O(logN)
O(N)
O(NlogN)
O(N​2​​)
作者: DS课程组
 
单位: 浙江大学
 
2-15
 
下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2） (2分)
 
冒泡排序
插入排序
堆排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-16
 
若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是： (2分)
 
冒泡排序
选择排序
插入排序
归并排序
作者: DS课程组
 
单位: 浙江大学
 
2-17
 
数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？ (2分)
 
冒泡排序
选择排序
插入排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-18
 
对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是： (2分)
 
冒泡排序
希尔排序
归并排序
基数排序
作者: DS课程组
 
单位: 浙江大学
 
2-19
 
就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是： (1分)
 
堆排序 < 归并排序 < 快速排序
堆排序 > 归并排序 > 快速排序
堆排序 < 快速排序 < 归并排序
堆排序 > 快速排序 > 归并排序
作者: DS课程组
 
单位: 浙江大学
 
2-20
 
下面四种排序算法中，稳定的算法是： (1分)
 
堆排序
希尔排序
归并排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-21
 
在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于O(NlogN)？ (1分)
 
冒泡排序
归并排序
希尔排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-22
 
下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(NlogN)的是： (1分)
 
冒泡排序
直接选择排序
堆排序
快速排序
作者: DS课程组
 
单位: 浙江大学
 
2-23
 
输入10​5​​个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是： (1分)
 
快速排序
插入排序
希尔排序
基数排序
作者: DS课程组
 
单位: 浙江大学
 
2-24
 
排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为： (1分)
 
插入排序
选择排序
快速排序
归并排序
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

归并排序(Merge Sort)是用分治策略（分治法）实现对n个元素进行排序的一种高速的、稳定的排序算法。
 
在介绍归并排序之前，我们首先简单的认识一下分治法
 
分治法
 
 
 
基本思想：
 将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
 精髓：
 分——将问题分解为规模更小的子问题。
 治——将这些规模更小的子问题逐个击破。
 合——将已解决的子问题合并，最终得到原问题的解。
 
 
在简单的了解过分治法之后，我们便开始介绍本文的“主角”——归并排序了。在正式介绍之前，再补充说明一下：归并排序是分治法的一个典型应用和完美体现，它是一种平衡的、简单的二分分治策略。
 
归并排序
 
 
 
基本思想：
 将原始数组A[0:n-1]中的元素分成两个大小大致相同的子数组：A[0:n/2]和A[n/2+1:n-1]，分别对这两个子数组单独排序，然后将已排序的两个数组归并成一个含有n个元素的有序数组。（不断地进行二分，直至待排序数组中只剩下一个元素为止，然后不断合并两个排好序的数组段）
 稳定性：
 归并排序包括不相邻元素之间的比较，但并不会直接交换。在合并两个已排序数组时，如果遇到了相同元素，只要保证前半部分数组优先于后半部分数组，相同元素的顺序就不会颠倒。
 复杂度：
 时间复杂度：
 归并排序算法的时间复杂度为O(nlogn)。（logn即为log2n）
 解析如下：
 当n=1时：T(n)=O(1)
 当n>1时：T(n)=2T(n/2)+O(n)
 其中，O(1)代表仅仅是计算出子序列的中间位置需要的常数时间。
 2T(n/2)代表递归求解两个规模为n/2的子问题所需的时间。
 O(n)代表合并算法可以在O(n)时间内完成。（因合并处理中，由于两个待处理的序列（局部数组）都已经完成了排序，因此可以在O(n1+n2)->O(n)时间内完成，n1指前半部分序列的长度，n2指后半部分序列的长度）
 解T(n)=2T(n/2)+O(n)由递推求解得：
 T(n)=2xT(n/2x)+xO(n)
 当递推最终的规模为1时，n/2x=1，那么x=logn
 则T(n)=nT(1)+logn*O(n)=n+lognO(n)=O(nlogn)
 空间复杂度：
 程序中变量占用了一些辅助空间，这些辅助空间都是常数阶，每合并一次会分配一个适当大小的缓冲区，且在退出时释放。最多分配大小为n，所以空间复杂度为O(n)。
 递归调用占用的栈空间是递归树的深度logn
 
 
在介绍完归并排序的基本思想、稳定性和复杂度之后，我们在看代码实现之前先看下图解了解一下。
 
 
 
归并排序中遇到的下标（标记）
 left代表序列在数组中的下界
 mid代表下界和上界的中间位置（mid=(left+right)/2）
 right代表序列在数组中的上界
 
 

 接下来我们举个例子来看一下当n为偶数的时候归并排序的过程以及合并操作过程的图解
 

 
 在看过图解之后，接下来就看下对应的代码实现：
 
 
 
辅助合并函数Merge(A,left,mid,right)，该函数将排好序列的两个子序列A[left:mid]和A[mid+1:right]进行合并。（整个算法的基础）
 
 
void Merge(int A[], int left, int mid, int right)             //合并操作的代码实现
{
	int *B = new int[right - left + 1];                       //申请一个辅助数组B[]，与传递过来的序列数组等长
	//图中的三个辅助标记（工作指针）
	int i = left;                                             //指向待排序子序列数组A[left:mid]中当前待比较的元素
	int j = mid + 1;                                          //指向待排序子序列数组A[mid+1:right]中当前待比较的元素
	int k = 0;                                                //k指向辅助数组B[]中待放置元素的位置

	while (i <= mid && j <= right)                             //当i和j都指向未超过数组范围的时候
	{                                                          //从小到大排序，将A[i]和A[j]中的较小元素放入B[]中
		if (A[i] <= A[j])                                      //当前半部分数组A[left:mid]的值不大于后半部分数组A[mid+1:right]的值时，将前半部分数组辅助标记对应的值存入辅助数组中（具有稳定性）
			B[k++] = A[i++];                                   //存入辅助数组B[]中，且与之对应的辅助标记后移
		else                                                   //否则将后半部分辅助标记对应的值存入B[]中
			B[k++] = A[j++];                                   //存入辅助数组且与之对应的辅助标记后移
	}

	while (i <= mid)                                           //对序列A[left:mid]剩余的部分依次进行处理，与图中的（5）对应
		B[k++] = A[i++];                                       //将辅助标记对应的值存入辅助数组中且辅助标记后移

	while (j <= right)                                         //对序列A[mid+1:right]剩余的部分依次进行处理
		B[k++] = A[j++];                                       //将辅助标记对应的值存入辅助数组中且辅助标记后移  

	for (i = left, k = 0; i <= right; i++)                     //将合并后的序列复制到原来的A[]序列
		A[i] = B[k++];

	delete[] B;                                                //释放动态创建的辅助数组空间
}
 
 
 
递归形式的归并排序函数MergeSort(A,left,right)
 1、将给定的包含n个元素的局部数组“分割”成两个局部数组。
 2、对两个局部数组分别执行归并排序。
 3、通过合并函数Merge(A,left,mid,right)将两个已排序完毕的局部数组“整合”成一个数组。
 
 
//递归形式的归并排序算法
void MergeSort(int A[], int left, int right)                   //归并排序
{
	if (left < right)                                          //当数组内的元素数大于1时进行二分操作，只有一个元素的时候，不作任何处理直接结束
	{
		int mid;
		mid = (left + right) / 2;                              //计算中间位置
		MergeSort(A, left, mid);                               //对数组A[left:mid]中的元素进行归并排序
		MergeSort(A, mid + 1, right);                          //对数组A[mid+1:right]中的元素进行归并排序
		Merge(A, left, mid, right);                            //进行合并操作
	}
}
 
在了解完代码实现后，看下归并排序的代码实现的执行顺序（与图解的联系）
 
 
归并排序的改进
 
 
 
1、在数组长度比较短的情况下不进行递归，而选择其他排序方案：如插入排序。
 2、归并过程中，可以用记录数组下标的方式代替申请新内存空间，从而避免A和辅助数组间的频繁数据移动。
 3、从分支策略的机制入手，容易消除算法中的递归：
 先将数组A中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，再将他们排序成长度为4的排好序的子数组段。如此继续下去，直至整个数组排好序。
 
 
//消去递归后的合并排序算法可描述如下：
void Merge(ElemType C[], ElemType D[], int left, int mid, int right)                               //合并C[left:mid]和C[mid+1:right]到D[left:right]
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= left && j <= right)
		if (C[i] <= C[j])
			D[k++] = C[i++];
		else
			D[k++] = C[j++];

	while (i <= mid)
		D[k++] = C[i++];

	while (j <= right)
		D[k++] = C[j++];
}

void MergePass(ElemType X[], ElemType Y[], int s, int n)       //函数MergePass()用于合并排好序的相邻数组段，具体的合并算法由Merge()函数来实现
{                                                              //合并大小为s的相邻子数组
	int i = 0;         

	while (i <= n - 2 * s)
	{
		Merge(X, Y, i, i + s - 1, i + 2 * s - 1);              //合并大小为s的相邻2段子数组
		i = i + 2 * s;                                         //标记后移
	}

	if (i + s < n)                                              //剩下的元素个数小于2s
		Merge(X, Y, i, i + s - 1, n - 1);
	else
		for (int j = i; j <= n - 1; j++)
			Y[j] = X[j];
}

void MergeSort(ElemType A[], int n)
{
	ElemType *B = new ElemType[n];                          //动态申请一个辅助数组
	int s = 1;
	while (s < n)                                           //当数组A[]中的元素个数大于1时
	{
		MergePass(A, B, s, n);                              //合并到数组B
		s += s;
		MergePass(B, A, s, n);                              //合并到数组A
		s += s;
	}
}
 
例题
 
题目描述
 
 
 
利用归并排序法将包含n个整数的数列S按升序排序
 
 
输入
 
 
 
输入有两行：第一行输入一个正整数n，第二行输入n个整数
 
 
输出
 
 
 
输出排序完毕的数列S，相邻的元素之间空格隔开
 
 
程序代码如下
 
#include<iostream>
#include<cstdlib>
#define ElemType_I int

using namespace std;

void Merge(ElemType_I A[], ElemType_I left, ElemType_I mid, ElemType_I right)             //合并
{
	ElemType_I *B = new ElemType_I[right - left + 1];                                     //申请辅助数组
	ElemType_I i = left;
	ElemType_I j = mid + 1;
	ElemType_I k = 0;

	while (i <= mid && j <= right)
		if (A[i] <= A[j])
			B[k++] = A[i++];
		else
			B[k++] = A[j++];

	while (i <= mid)
		B[k++] = A[i++];

	while (j <= right)
		B[k++] = A[j++];

	for (i = left, k = 0; i <= right; i++)
		A[i] = B[k++];

	delete[] B;
}

void MergeSort(ElemType_I A[], ElemType_I left, ElemType_I right)                             //递归形式的归并排序
{
	if (left < right)
	{
		ElemType_I mid;
		mid = (left + right) / 2;
		MergeSort(A, left, mid);
		MergeSort(A, mid + 1, right);
		Merge(A, left, mid, right);
	}
}

int main()
{
	ElemType_I n;
	cin >> n;
	ElemType_I *A = new ElemType_I[n];
	for (int i = 0; i < n; i++)
		cin >> A[i];

	MergeSort(A, 0, n - 1);                                          //调用归并排序              

	for (int i = 0; i < n; i++)
		cout << A[i] << " ";

	cout << endl;
	//system("pause");                                                        //输出暂停，头文件<cstdlib>

	return 0;
}
 
程序运行结果如下
 

 [注释1]：当n为奇数时的图解以及稳定性的图解与上述类似，因此就不再进行描述了。归并排序也可以将数组分成A[left:mid]和A[mid:right]，其中left指局部数组的开头元素，right指局部数组末尾+1的元素，A[left:mid]包括left到mid（不包括mid），A[mid:right]包括mid到right（不包括right），但其代码实现和图解需要部分修改。
 [注释2]：基于关键字比较的排序算法的平均时间复杂度的下界为O(nlogn)