Natural merge sort

liuxinyu95

通常我们见到的merge sort的思路是典型的分而治之divide and conquer策略：
1. 如果待排序序列为空，或者只有1个元素，结束
2. 否则，将序列一分为二，将两个子序列分别merge sort，再将两个排好的子序列merge

我们也可以从另外一个角度出发，序列中存在一些已经排好的片段，我们可以把这些排好的片段merge起来，不断重复直到序列排好（只含有一个排好的片段，亦即整个序列）
这种思路叫做natural merge sort。

例如下面的Haskell代码：
mergesort' = foldl merge [] . groupBy' (<=)

其中merge的实现非常简单：
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys

早期的Haskell 标准库中的groupBy (<=) xs可以把xs分成若干已序的小片段，例如：
groupBy (<=) [1, 5, 2, 7, 8, 10] 的结果是 [[1, 5], [2, 7], [8, 10]]

但是最新的标准库这样不可以了，原因是groupBy 接受一个用于判断相等的函数，相等必须满足：自反性、传递性和对称性
亦即：
x = x
x = y, y = z 则 x = z
x = y 则 y = x

而小于等于显然不满足。故而我写了一个groupBy'，用于切割已序片段：
                                
groupBy' :: (a->a->Bool) ->[a] ->[[a]]
groupBy' _ [] = [[]]
groupBy' _ [x] = [[x]]
groupBy' f (x:xs@(x':_)) | f x x' = (x:ys):yss
                         | otherwise = [x]:r
  where
    r@(ys:yss) = groupBy' f xs

注意，这个算法可以近一步提高。我们遍历已序序列，不断使用merge，其实我们可以针对已序序列，两两merge，然后对其结果在迭代地两两merge，
这就是典型的bottom up merge sort的思路，算法改进如下：

mergesort = concat . mergePairs . groupBy' (<=) where
  mergePairs (xs:ys:xss) = mergePairs ((merge xs ys) : (mergePairs xss))
  mergePairs xss = xss

D. Knuth在TAOCP(计算机程序设计艺术)中，给出的略有不同，是一种2-way natural merge sort，思路有些类似quick sort
我们同时从一个序列的头部和尾部向中间检查：
1.  从头部取出一个最长的升序子序列；
2.  从尾部取出一个最长的降序子序列；
3.  将结果merge到一个目标序列的头部，然后重复1, 2，下次将结果merge到目标序列的尾部
4.  重复1, 2, 3，直到待排序序列已序（从头部取出的最长升序序列，就是整个序列）

相应的python代码如下：
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/n2_merge_sort.py

C代码：
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/n2_merge_sort.c

全部源代码可以在github下载。
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/sorting/merge-sort/src/NMergeSort.hs


PS: 我们不讨论merge sort的优劣或者和Quick sort PK, 具体讨论可参见wikipedia
http://en.wikipedia.org/wiki/Merge_sort