本文记述了归并排序的 3 项改进和一份参考实现代码，并在说明了算法的性能后用随机数据进行了验证。
◆ 思想
本文实现了《算法（第4版）》书中提到的 3 项改进，
- 对小规模子数组使用插入排序。减少在小规模数组中的递归调用能改进整个算法。
- 测试数组是否已经有序。任意有序的子数组算法的运行时间变成线性的。
- 不将元素复制到辅助数组。可以节省将数组元素复制到用于归并的辅助数组所用的时间。
◆ 实现
排序代码采用《算法（第4版）》的“排序算法类模板”实现。(代码中涉及的基础类，如 Array，请参考算法文章中涉及的若干基础类的主要API）
// merge3.hxx
...
class Merge3
{
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
void
sort(Array<_T> & a)
{
int N = a.size();
Array<_T> aux = Array<_T>(N);
for (int k = 0; k < N; ++k) // #3
aux[k] = a[k];
__sort__(aux, 0, N-1, a); // #4
}
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
void
__sort__(Array<_T> & a, int lo, int hi, Array<_T> & aux)
{
if (hi - lo <= 15) { // #1
for (int i = lo+1; i <= hi; ++i)
for (int j = i; j > lo && __less__(aux[j], aux[j-1]); --j)
__exch__(aux, j, j-1);
} else {
int mi = lo + (hi - lo) / 2;
__sort__(aux, lo, mi, a); // #5
__sort__(aux, mi+1, hi, a);
if (__less__(a[mi], a[mi+1])) // #2
for (int i = lo; i <= hi; ++i)
aux[i] = a[i];
else
__merge__(a, lo, mi, hi, aux);
}
}
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
void
__merge__(Array<_T> & a, int lo, int mi, int hi, Array<_T> & aux)
{
int i = lo, j = mi+1;
for (int k = lo; k <= hi; ++k)
if (i > mi) aux[k] = a[j++];
else if (j > hi) aux[k] = a[i++];
else if (__less__(a[j], a[i])) aux[k] = a[j++];
else aux[k] = a[i++];
}
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
bool
__less__(_T const& v, _T const& w)
{
return v.compare_to(w) < 0; // #6
}
...
当待排序的子数组规模较小时，采用插入排序（#1）。测试数组是否已经有序，可确保有序的子数组算法的运行时间变成线性的（#2）。为了节省将数组元素复制到用于归并的辅助数组所用的时间，排序开始前先做一次复制（#3），然后在递归调用的每个层次交换输入数组和辅助数组的角色，先将数据从输入数组排序到辅助数组（#5），再将数据从辅助数组排序到输入数组（#4）。将 '<' 改为 '>'，即得到逆序的结果（#6）。
◆ 性能
| 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|
| N*log(N) | N | 是 |
◆ 验证
测试代码采用《算法（第4版）》的倍率实验方案，用随机数据验证其正确性并获取时间复杂度数据。
// test.cpp
...
time_trial(int N)
{
Array<Double> a(N);
for (int i = 0; i < N; ++i) a[i] = Std_Random::random(); // #1
Stopwatch timer;
Merge3::sort(a); // #2
double time = timer.elapsed_time();
assert(Merge3::is_sorted(a)); // #3
return time;
}
...
test(char * argv[])
{
int T = std::stoi(argv[1]); // #4
double prev = time_trial(512);
Std_Out::printf("%10s%10s%7s\n", "N", "Time", "Ratio");
for (int i = 0, N = 1024; i < T; ++i, N += N) { // #5
double time = time_trial(N);
Std_Out::printf("%10d%10.3f%7.2f\n", N, time, time/prev); // #6
prev = time;
}
}
...
用 [0,1) 之间的实数初始化待排序数组（#1），打开计时器后执行排序（#2），确保得到正确的排序结果（#3）。整个测试过程要执行 T 次排序（#4）。每次执行排序的数据规模都会翻倍（#5），并以上一次排序的时间为基础计算倍率（#6），
此测试在实验环境一中完成，
$ g++ -std=c++11 test.cpp std_out.cpp std_random.cpp stopwatch.cpp type_wrappers.cpp
$ ./a.out 15
N Time Ratio
1024 0.007 2.33
2048 0.015 2.14
4096 0.032 2.13
8192 0.070 2.19
16384 0.149 2.13
32768 0.315 2.11
65536 0.667 2.12
131072 1.405 2.11
262144 2.952 2.10
524288 6.189 2.10
1048576 12.941 2.09
2097152 27.072 2.09
4194304 56.800 2.10
8388608 118.166 2.08
16777216 245.443 2.08
可以看出，随着数据规模的成倍增长，排序所花费的时间将是上一次规模的 2.1? 倍，且在不断变小。将数据反映到以 2 为底数的对数坐标系中，可以得到如下图像，
O(N*log(N)) 代表了线性对数级别复杂度下的理论排序时间，该行中的数据是以 Time 行的第一个数据为基数逐一乘 2 + 2/log(N) 后得到的结果（因为做的是倍率实验，所以乘 (2*N*log(2*N)) / (N*log(N))，化简得到 2 + 2/log(N)，即乘 2+2/log(1024)，2+2/log(2048)，2+2/log(4096)，... 2+2/log(16777216)；因为是二分归并，所以 log 的底数为 2）。
◆ 最后
完整的代码请参考 [gitee] cnblogs/18191308 。
写作过程中，笔者参考了《算法（第4版）》的归并排序、练习题 2.2.11、“排序算法类模板”和倍率实验。致作者 Sedgwick，Wayne 及译者谢路云。
标签：__,归并,log,int,算法,数组,aux,排序 From： https://www.cnblogs.com/green-cnblogs/p/18191308