本文记述了自然的两两归并排序并给出了一份参考实现代码。在说明了算法的性能后用随机数据进行了验证。
◆ 思想
自然的归并排序是自底向上的。先从第一个元素开始找到一个有序的子范围，然后从紧接着的后面元素开始找到另一个有序的子范围，将这两个子范围归并成一个大的有序子范围。接着找到下一个有序子范围，将它与前面的有序子范围归并。重复以上步骤，直到所有元素都被归并，即得到完整有序的结果。
◆ 实现
排序代码采用《算法（第4版）》的“排序算法类模板”实现。(代码中涉及的基础类，如 Array，请参考算法文章中涉及的若干基础类的主要API）
// merge5.hxx
...
class Merge5
{
...
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)
aux[k] = a[k];
int lo = 0, mi = 0, hi = 1;
while (hi < N) {
__merge__(a, lo, mi, hi, aux); // #1
mi = hi++;
while (hi < N-1 && __less__(a[hi], a[hi+1])) ++hi; // #2
}
}
...
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 = hi;
for (int k = lo; k <= mi; ++k)
aux[k] = a[k];
for (int k = mi+1; k <= hi; ++k) // #3
aux[k] = a[hi - (k - (mi+1))];
for (int k = lo; i <= j; ++k)
if (__less__(aux[i], aux[j])) a[k] = aux[i++];
else a[k] = aux[j--];
}
...
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; // #4
}
...
先从 [0,0] 和 [1,1] 这两个有序子范围开始，将两个有序子范围归并（#1）成一个大的有序子范围，然后找到下一个有序子范围（#2），再把这两个有序子范围进行归并（#1）。此处的归并使用了归并排序（四）中的快速归并方案（#3）。重复以上步骤，直到所有元素都被归并，即得到完整有序的结果。将 '<' 改为 '>'，即得到逆序的结果（#4）。
◆ 性能
对 __merge()__ 函数的改进，导致了不稳定的归并。
| 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|
| N^2 | 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;
Merge5::sort(a); // #2
double time = timer.elapsed_time();
assert(Merge5::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 8
N Time Ratio
1024 0.201 4.02
2048 0.819 4.07
4096 3.267 3.99
8192 12.630 3.87
16384 51.466 4.07
32768 205.775 4.00
65536 836.357 4.06
131072 3312.554 3.96
可以看出，随着数据规模的成倍增长，排序所花费的时间将是上一次规模的 4 倍。将数据反映到以 2 为底数的对数坐标系中，可以得到如下图像，
O(N^2) 代表了平方级别复杂度下的理论排序时间，该行中的数据是以 Time 行的第一个数据为基数逐一乘 4 后得到的结果（因为做的是倍率实验，所以乘 (2)^2 即 4）。
◆ 最后
完整的代码请参考 [gitee] cnblogs/18207655 。
写作过程中，笔者参考了《算法（第4版）》的归并排序、练习题 2.2.16、“排序算法类模板”和倍率实验。致作者 Sedgwick，Wayne 及译者谢路云。
标签：__,归并,int,算法,hi,time,排序 From： https://www.cnblogs.com/green-cnblogs/p/18207655