常见七大排序（汇总）

引言

交换函数

直接插入排序

思想

时间复杂度

希尔排序

思想

时间复杂度

选择排序

思想

时间复杂度

堆排序

思想

时间复杂度

冒泡排序

思想

时间复杂度

快速排序（递归）

霍尔法

前后指针法

三数取中 & 随机值法

第一种是随机值法

第二种是三数取中

快速排序（非递归）

归并排序（递归）

思想

时间复杂度

归并排序（非递归）

测试验证（100万个数测试看强度）

总代码（gitee）

结语

引言

本篇文章会对常见的七大排序进行讲解：

直接插入排序 InsertSort
希尔排序 ShellSort
选择排序 SelectSort
堆排序 HeapSort
冒泡排序 BubbleSort
快速排序 QuickSort
归并排序 MergeSort

其中，快排与归并排序除了讲解递归版本之外，还会讲解一下非递归的版本

交换函数

这是一个小的函数，只是后面会频繁用到，这里就简单做一下逻辑的分离

Swap函数代码如下：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

直接插入排序

思想

直接插入排序就好像我们平时打扑克牌，每次拿到牌的时候都会洗牌

我们每张牌都会用到，我们抽取出其中一张牌，然后将其插入到对应的位置上，当我们把每一张牌都如上操作插入一遍之时，我们就排序好了

如下图：

如上我们会看到：在换到 2 的时候最为特殊，他在交换了一次之后并没有停下，而是不断让前面的数跟他比较，在前面没有比他大的数字的时候，才插入下来

而这个逻辑的实现也较为容易，我们只需要创建一个变量（end），这个变量代表着这是数组中的第几个数，再将该变量的下一个数给存起来，记作 int tmp = a [ end + 1 ]

如果 end 变量的下一个（是跟tmp比较）比他小（假设排升序，左小右大），那么我们就让 end 变量代表的数将其覆盖，随后 end--。设置一个循环，当 end 减小到 <0 时，就代表 tmp 存的数是整个数组里面最小的一个

这时我们再让 tmp 将 end + 1 位置的数给覆盖

注：因为不是每一个数都是最小的，我们用 end 的数将 end + 1 位置的数给覆盖了之后，原本 end 位置的数就空出来了，但是我们的 end 是先减减，然后才判断的，所以 tmp 覆盖的位置应该是 end + 1

如果不理解的话，也可以参考下图：

插入排序代码如下：

//直接插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

因为 end + 1 位置的数据会被覆盖，所以需要提前存一份

我们 while 循环的条件是 end >= 0，如果 end + 1 位置的数大于 tmp 代表的数，就覆盖，并end--

时间复杂度

这个排序的时间复杂度也比较好算，每个数都要由第一个 for 循环遍历一遍

遍历每一个数时还要将每个数再遍历一遍

所以该数的时间复杂度为 O(N^2)

希尔排序

思想

我们学完了插入排序之后，我们会发现每个数都是拿出来，找位置，交换，就像是打扑克牌刚拿到牌时洗牌一样，拿一张，挑合适的位置，插入，如此反复

如上图，每一次交换都是两张两张之间进行的

但是，大佬希尔发现了不对劲

如果需要排序的数组接近有序的话，那么直接插入排序的效率将会非常高

所以大佬就想着，能不能在直接插入排序的基础上进行改进，在两张两张之间排序之前，先将其变成接近有序的

这就是——预排序

不一定非要两个两个，让其跨度大一点呢？

多来几组呢？

让这些个组先粗略地排一遍，那么不就接近有序了！

但是只是跨一个，或是两个，抑或是三个之间交换，这样子排似乎不够

最后希尔大佬发现，先让间隔 gap 等于排序数组总数的一半，在进行完一次预排序之后，再让 gap 除等 2，一直循环，直到 gap<1 ，这时候的效率是最高的，时间复杂度接近 O(N*logN)

这是非常快的！

拿N^2 与 N*logN对比一下

假设有100万个数据

2^20 为1’048‘576，接近100万，且当作100万来算

N^2 要排序 100万 * 100万次

N*logN 大概要排序 100万*20次

快了不是一点半点！！！

但是后来，有人发现，我们不需要分那么多组，太麻烦了

我们可以只用一组，让这一组拍完之后不断向后移动即可，如下：

我们先将其中一次的逻辑实现一遍：

先假设 gap = 3

那么我们就是将每个间隔对应位置的数给排好

假如我们现在要排的是如下图所示的 3

那么我们就需要先将 3 和 1 进行对比

如果 3 大于 1，那么我们就用 3 将 1 给覆盖，由于要被覆盖，所以我们需要先将 1 位置的数据先存起来，记作 tmp

由于数据是从前往后排的，我们只是截取了 3 这个点作为例子，因此，3 前面的数据肯定是已经排序好了的

接着，我们让 1 和 2 进行比较，2 > 1，所以 2 将原本 3 的位置给覆盖

最后当 1 无法向后再走的时候，1 再将原本 2 的位置给覆盖掉

这其实和我们上文提到的直接插入排序的思路是一摸一样的，如果有疑惑的，可以将上文插入排序的逻辑理一理

单次预排序代码如下：

int gap = 3;

int end = i;//假设i位置就代表我们说的3的位置
int tmp = a[end + gap];
while (end >= 0)
{
	if (a[end] > tmp)
	{
		a[end + gap] = a[end];
		end -= gap;
	}
	else
		break;
}
a[end + gap] = tmp;

在加上希尔大佬的想法：先设gap为总数的一半，再不断将其除等 2

当 gap 为 1 的时候，其实就是直接插入排序

综上，总代码如下：

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

时间复杂度

具体时间复杂度的算法涉及到数学中的概率等等知识点，讲明白的时候已经是数学问题了，所以各位可以直接记结论

接近 O(N*logN)

选择排序

思想

其实选择排序很好理解,其主要思想就是：

定义出变量begin和end，begin初始化为0，end为n-1（共有n个元素）

不断地遍历数组，每遍历一次，就找出最小值和最大值，再将这两个分别放到begin和end位置上

最后begin++，end--

每一次都找到begin与end范围内的最大与最小

代码（有坑的，待会儿填）如下：

int begin = 0, end = n - 1;
while (begin < end)
{
	int mini = begin, maxi = begin;
	for (int i = begin + 1; i <= end; i++)
	{
		if (a[i] < a[mini])mini = i;
		if (a[i] > a[maxi])maxi = i;
	}
	Swap(&a[begin], &a[mini]);
	Swap(&a[end], &a[maxi]);
	begin++, end--;
}

如果这时候你去运行代码，你会发现结果是错误的，而且出错的是最中间的两个元素

我们用图解的方式来了解一下为什么：

我们会发现，到了最后一步的时候，begin先和min换一次，但是end和max又换回来了

也就是说，本来是换好了的，但是换了两遍又换回来了

所以我们可以加个判断：当begin等于max的时候，我们就将max的值赋值为min

最后的结果就是end自己和自己换了一次，结果就正确了

完整代码如下：

//选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])mini = i;
			if (a[i] > a[maxi])maxi = i;
		}
		Swap(&a[begin], &a[mini]);
		if (begin == maxi)maxi = mini;
		Swap(&a[end], &a[maxi]);
		begin++, end--;
	}
}

时间复杂度

不难看出，每个数都遍历一遍的同时，都会再找一遍最大值和最小值

所以时间复杂度是 O(N^2)

堆排序

思想

堆排序的核心思想就是建堆，升序建大堆，降序建小堆

我们先来说一下堆已经建好了的情况下，我们该怎么排序：（这里假设我们排的是升序）

这是一个已经建好了的大堆

我们先将最末尾的数字与最顶上的数字进行交换，由于顶上的数字是最大的，所以交换完之后，就代表这个数字已经被排好了

你可以理解成是从后面开始往前排

交换完了之后，我们让控制总数的那个变量减减一下，那么总数就少了一个，代表最后一个已经排序好的数字就不会再受到干扰了

最后对这个大堆进行向下调整，再一次选出最大的那个数字放在堆顶，交换，减减，向下调整，如此往复

图解如下：

建堆和排序代码如下：

void HeapSort(int* a, int n)
{
	//建大&小堆
	for (int i = (n - 2) / 2; i >= 0; i--)
		AdjustDown(a, n, i);

	//首尾交换 + 排序
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end--, 0);//向下调整
	}
}

接着我们再来讲一讲向下调整法：

向下调整法本质上，设当前节点为父节点，先在两个子节点里面找到大的那一个（假设此处是建大堆）

对比父节点与大的那个子节点，父节点大就终止循环，子节点大就交换两节点，以子节点为新的父节点，往下n*2+1个位置的节点作为新的字节点

当子节点 > 数组总个数时，退出循环

补充一个点，我们可以使用假设法找到两个子节点中大的那个节点

先假设其中一个是大的那个

再 if 判断一下：如果该节点没有另一个大，就换成另一个为子节点，相反则不做处理

向下调整代码如下：

//堆排序(升序建大堆√，降序建小堆)
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		//假设法找大孩子
		if (child + 1 && a[child] < a[child + 1])child++;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
	}
}

时间复杂度

由于堆排序是二叉树结构，树的高度是logN

我们可以推理一下公式：

树的总数：N = 2^0 + 2^1 +......+ 2^(n-1)

树的总高度为 n-1

N = 2^0 + 2^1 +......+ 2^(n-1)

2N = 2^1 + 2^2 +......+ 2^n

上述两式相减：N = 2^n - 2^0 = 2^n - 1

所以树的高度大致为 logN

所以就是遍历了 N*logN 次

时间复杂度就是 O(N*logN)

冒泡排序

思想

冒泡排序本质上就是一个 for 循环嵌套

外层的for循环代表的是一共要进行多少趟冒泡

嵌套在里面的那一层代表的是每一趟冒泡的具体过程

每一趟冒泡就是（假设要升序）：如果后一个比前一个小，那么就交换

第一趟冒泡结束之后，最大的那个数字就被排好了；第二趟冒泡之后，第二大的就被排好了，如此往复

代码如下：

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
				Swap(&a[j], &a[j + 1]);
		}
	}
}

时间复杂度

O(N^2)

快速排序（递归）

霍尔法

霍尔法的本质思想就是：先将最左边的数定义为key

然后两个变量begin和end，分别从左边与右边出发

为了保证最后停下位置的数一定比key要小，所以需要end先从右边走

如果遇到比 key 小的数，那么 end 就停下来

接着 begin 走，如果遇到的数比 key 要大，也停下来

最后交换 begin 和 end

接着，一个从右边出发，一个从左边出发，不断反复，直到 begin >= end，终止循环

当循环终止的时候，就代表着 begin 和 end 指向一个地方

这样子做完之后，最后的结果就是key位置的数排好了，key左边的数都比key代表的数要小，右边的都比key代表的数要大

图解如下：

当我们将上图中的5给排好了之后，我们可以使用递归的方法，左边和右边都使用上述同样的方法，我们需要传的是一个范围

原函数开始是传 0 和 7（一共8个数）

排序完了之后，我们就分别传 0 key-1，key+1 7

每一个排序完了之后，我们都按这种方法不断递归下去

图解如下：

既然是递归，那么就肯定需要返回条件，如若不然则会无限递归下去

由上图可得，返回条件有两种情况：

此时 2 是key

key 的左边还有数，所以传过去的范围就是一样的，即 begin == key-1
key 的右边没有数，所以传过去的范围是 key-1 > end

综上，我们可以知道返回条件是：if（left >= right） return;

综上，代码如下：

//快排
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
		return;

	int begin = left, end = right;
	int key = left;

	while (left < right)
	{
		//right先走
		while (right > left && a[right] >= a[key])right--;
        //left走
		while (right > left && a[left] <= a[key])left++;

		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	key = left;

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

前后指针法

实际上，这种方法比霍尔法更为方便，只不过毕竟是霍尔大佬整出的快排，学快排肯定要学一下霍尔法

而前后指针的逻辑也很简单

我们有一前一后两个指针，我们最后的目的是让两个指针之间的数为大于 key 的数（升序），而前指针左边的数都是小于 key 的数

最后将 key 与前指针交换，就达到了和霍尔法一样的效果

其主要思想如下：

前面的指针为 prev，后面的指针为 cur，记最左边的那个数为 key

如果 cur 指向的值 < key 指向的值（升序），那么我们就将 prev++，接着交换 prev 和 cur，最后 cur++，如果 cur 指向的值 > key 指向的值，那么直接 ++cur 即可

因为我们需要达到的结果是：prev 和 cur 之间包含的是 > key 的值，而由于最后的步骤是将 prev 和 key 进行一个交换，之后再进行递归，所以 prev 的值是应该小于 key 代表的值的

这时我们需要分几种情况的分析：

prev 的下一个就是 cur（cur 代表的值 < key 代表的值）：由于 prev 是需要小于 key 的，所以如果 prev 的下一个就是 cur 的话，那么就意味着 prev 和 cur 之间可以不包括这个数据，按照如上的做法，我们先++prev，然后交换 prev 和 cur（自己和自己换），再++cur，结果是对的
prev 与 cur 之间有值（cur 代表的值 > key 代表的值）：由于 prev 和 cur 之间包含的值是大于 key 的，所以直接 cur++ 即可
prev 与 cur 之间有值（cur 代表的值 < key 代表的值）：我们先++prev，由于 prev 和 cur 之间的值都是大于 key 的值，所以++prev 之后的就是大于 key 的值，由于现在 cur 指向的值 < key，所以我们就将 prev 和 cur 交换一下，这样就达成了我们的目的

图解如下：

上述逻辑的代码如下（未改进前的版本）：

int key = left;
int prev = left;
int cur = right;

while(cur <= right)
{
    if(a[cur] < a[key])
    {
        ++prev;
        Swap(&a[prev], &a[cur]);
        ++cur;
    }
    else
    {
        ++cur;
    }
    ++cur;
}
a[key] = a[prev];
key = prev;

但是有人觉得这样子写太啰嗦了，反正 cur 都是要++的，干脆合在一起算了

所以就有了下面的代码：

int prev = left, cur = prev + 1;

int key = left;
while (cur <= right)
{
	if (a[cur] < a[key] && ++prev != cur)
		Swap(&a[prev], &a[cur]);
	++cur;
}
Swap(&a[prev], &a[key]);
key = prev;

再加上递归和返回条件

总代码如下：

void QuickSort(int* a, int left, int right)
{
	if (left < right)
		return;
	int prev = left, cur = prev + 1;

	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
			Swap(&a[prev], &a[cur]);
		++cur;
	}
	Swap(&a[prev], &a[key]);
	key = prev;

	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

三数取中 & 随机值法

快排好是好，但是他也分情况

由于快排每一次都是排序好一个位置的数，然后再将左边和右边分为两个区间，再不断递归下去的

快排最好的情况就是：

每次都是在最中间的位置分出左右区间，随后递归，这时时间复杂度为O(N*logN)

快排最坏的情况就是：

每次都是在最边边的位置选区间，也就是接近有序的情况，这时时间复杂度接近 O(N^2)

所以如果面临的要排序的数组接近有序的话，我们该如何处理这种情况呢？

第一种是随机值法

随机值法就是：从数组中随机选一个数，将这个数与 key 位置的数字进行交换，以这个数作为新的 key

代码如下：

int randi = rand() % (right - left);
randi += left;
Swap(&a[left], &a[randi]);

由于我们写的是递归，我们选的数字可能并不是从 0 位置开始的，所以 randi 要 += left 保证 randi 在的位置是待排序那一段数组的起始位置

第二种是三数取中

有人觉得按随机值法不太可靠，不太稳定，不是很喜欢，所以就发明了这种三数取中的方法

三数取中法的本质就是：

将待排序数组的头、尾、中间位置的数进行比较，将排在中间位置的值返回

如果待排序数组接近有序的话，我们用一手三数取中，不就可以尽可能地保证，快排在中间位置分左右区间再递归吗？这多有效率啊

具体逻辑就是比较，这里不做过多解释

三数取中代码如下：

int GetMid(int* a, int left, int right)
{
	int mid = (right + left) / 2;

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] < a[right])
			return right;
		else
			return left;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}

快速排序（非递归）

快速排序的非递归版本，主体上和递归版本没有什么区别，逻辑还是那个逻辑，还是前后指针法、霍尔法完成选数字分区域

唯一不同的就在于：

以前我们对分完区域后的数组段是递归处理

现在我们是用栈 + 循环的方式来模拟实现递归的

我们将区域压入栈内，比如先压 0 9 ，后面可能会压 0 5，7 9 ，不断重复下去

我们每排完一次序，我们就从栈里面取数据，再用取出的这两个数据进行压栈

你会发现，我们每从栈里面取一次数据，就相当于进行了一次递归的过程

而当栈里面没有数据了的时候，也就代表我们已经排序好了

由于C语言不像C++有 stl库可以直接使用，所以我们只能现场手撕一个

为了不耽误大家时间，我在这里就简单介绍一下我会使用到的关于栈的函数名：

STInit 栈的初始化
STPush 压栈
STPop 出栈
STEmpty 判断栈是否为空
STDestroy 销毁

由于主题逻辑和递归是一摸一样的，这里就直接放代码了

代码如下：

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);

		int end = STTop(&st);
		STPop(&st);

        //单趟排序
		int key = begin;
		int prev = begin;
		int cur = begin + 1;

		while (cur <= end)
		{
			if (a[cur] < a[key] && ++prev != cur)
				Swap(&a[prev], &a[cur]);

			++cur;
		}

		Swap(&a[key], &a[prev]);
		key = prev;

		if (key + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, key + 1);
		}

		if (begin < key-1)
		{
			STPush(&st, key-1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

归并排序（递归）

思想

我们先通过一张图片来看一看，归并排序是一个什么东西：

你可以理解成，先将待排序数组以二叉树的形式分好，再从底层开始一个一个排

当然你也可以说，这是后序

同时我们还需要另外 malloc 一块空间，因为我们是通过选数的方式，将小的数（升序）先放到数组里面，然后再 memcpy 回原数组，中间需要一个不被销毁的中转站

我们将 malloc 出来的这块空间且指向这块空间的指针称为 tmp

我们将这一段待排序数组分成以 mid 为中心的两个区域，begin->mid mid+1->end

随后我们将这两段进行排序，设左边的那段为左数组，右边那段为右数组

我们这样判断：左数组的第一个和右数组的第一个比，谁小就先将其放在 tmp 数组里面

再不断地比较下去，直到有一边没有数字了，循环终止

接着我们还需要各自判断一遍：左数组还有没有数，如果有，就证明左数组里剩下的数比右数组的都要大，就将其依次放入 tmp 中

右数组同理

图解如下：

如果 begin 和 end 相等的话，就代表现在递归到只剩一个数了，这时就返回

所以我们的递归判断条件是：if（end == begin）return;

代码如下：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin == end)
		return;

	int mid = (begin + end) / 2;
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int i = begin;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while(begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

时间复杂度

由于这是一个树结构，树的高度为 logN，待排序数组有 N 个数

所以时间复杂度为 O(N*logN)

归并排序（非递归）

由于递归给 ban 掉了，所以我们现在首要的问题就是：如何先两两排，再四四排等等，就像递归一样

我们核心逻辑不变，还是两个数组段之间进行比较，还是需要 malloc 出一块 tmp 数组作为中转站

这时我们可以引入一个 gap

gap 代表的是当前是多少个数之间进行比较，图解如下：

但是由于并不是每一个数组都是偶数，而且即使是偶数个，之后也会出现越界的情况，所以我们需要分开讨论

我们对区域的划分创建了四个变量：

begin1
end1
begin2
end2

其中，除了 begin1 不会出现越界情况之外，其他的每一个变量都会出现越界的情况

如果是 end1 或 begin2 越界了的话，我们就不用再排序下去了

end1：假设有数组段 0 3，4 8，9 10。这时我们就可以让 0 3，4 8 这两个数组之间排，排完了之后再让 0 8，9 10 两个数组之间排，所以 end1 越界无需接着排序下去
begin2：假设有数组段 0 3，4 8，9 13，begin2 越界就代表着在场的数组段为奇数段，有一段没有对应的数组两两比较，所以 begin2 越界也无需接着排序下去
end2：如果是 end2 越界，而其他变量没有越界的话，那么就意味着场上的数组为奇数个，只是最后两个数组可能一个有 6 个数，另一个有 4 个数，不一样而已，所以 end2 越界我们还是要接着排序下去的，只是我们需要改一下 end2 的值，如果共有 n 个数的话，我们就需要将 end2 赋值为 n-1（因为 end2 代表的是一个位置，end2 越界时，数组最后一个数的位置就是最后一个数组的边界）

综上：我们要将这几个变量控制好，排序才不会出错，控制代码如下：

if (begin2 >= n || end1 >= n)
	break;
if (end2 >= n)
	end2 = n - 1;

而我们第一次排序时，每组都为 gap=1 个数，而后不断将其乘等2

而循环结束的条件就是：当 gap < n 时，退出循环

整体代码如下：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		for (int j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = begin1 + gap - 1;
			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;

			if (begin2 >= n || end1 >= n)
				break;
			if (end2 >= n)
				end2 = n - 1;

			int i = j;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
					tmp[i++] = a[begin1++];
				else
					tmp[i++] = a[begin2++];
			}
			while (begin1 <= end1)
				tmp[i++] = a[begin1++];
			while (begin2 <= end2)
				tmp[i++] = a[begin2++];

			memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));
		}
		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}