当前位置 博文首页 > 屎壳郎的博客：[Alg]排序算法之归并排序
作者：屎壳郎 miaosg01@163.com
日期：Aug 2021
版次：初版
简介： 归并排序是一类在任何情况下都能保证 N lg ? ( N ) N\lg(N) Nlg(N)的排序算法，它在数据量比较小时体现的不明显，但在大数据量时优势明显。归并排序在外部排序中尤其重要，由于受到外部存储条件的限制，归并排序几乎是唯一选择。
设有两个有序的序列1 4 6 8与2 3 5 7，我们比较头部两个较小的项，然后输出最小者，然后重复这个步骤直到两个序列都清空。
∣
1
￣
2
￣
4
3
6
5
8
7
\bigg|{\underline1\atop\underline2} {4\atop3}{6\atop5}{8\atop7}
∣∣∣∣?2?1??34?56?78?
1
∣
4
￣
2
￣
6
3
8
5
7
1\bigg|{\underline4\atop\underline2}{6\atop3}{8\atop5}{ \atop7}
1∣∣∣∣?2?4??36?58?7?
1
??
2
∣
4
￣
3
￣
6
5
8
7
1\;2\bigg|{\underline4\atop\underline3}{6\atop5}{8\atop7}
12∣∣∣∣?3?4??56?78?
当有一个序列耗尽时，需要特别处理，详细算法描述如下：
两个非空的已排好序的序列 x 1 ≤ x 2 ≤ ? ≤ x m x_1\leq x_2\leq\cdots\leq x_m x1?≤x2?≤?≤xm?和 y 1 ≤ y 2 ≤ ? ≤ y n y_1\leq y_2\leq\cdots\leq y_n y1?≤y2?≤?≤yn? 归并为一个有序序列 ( z 1 ≤ z 2 ≤ ? ≤ z m + n ) (z_1\leq z_2\leq\cdots\leq z_{m+n}) (z1?≤z2?≤?≤zm+n?)。
