这是 Haskell 中正确实施的合并排序吗？

Question

我在网上的任何地方都找不到我的代码，所以你能告诉我为什么 myMergeSort 函数不是归并排序吗？我知道我的函数 myMergeSort 排序，但我不确定它是否真的使用合并排序算法进行排序，或者它是否是不同的算法。我几天前刚开始Haskell。

merge xs [] = xs
merge [] ys = ys
merge (x : xs) (y : ys)
    | x <= y = x : merge xs (y : ys)
    | otherwise = y : merge (x : xs) ys

myMergeSort :: [Int] -> [Int]
myMergeSort [] = []
myMergeSort (x:[]) = [x]
myMergeSort (x:xs) = foldl merge [] (map (\x -> [x]) (x:xs))

我对 merge 函数没有任何疑问。

下面的函数 mergeSortOfficial 是提供给我们的解决方案，我理解它但不确定我是否在我的函数 myMergeSort[ 中实现了合并排序算法=26=]正确与否。

官方解决方案-实现：

mergeSortOfficial [] = [] mergeSortOfficial (x : []) = [x] mergeSortOfficial xs = merge (mergeSortOfficial (take ((length xs) ‘div‘ 2) xs)) (mergeSortOfficial (drop ((length xs) ‘div‘ 2) xs))

Answer 1

myMergeSort 不是正确的合并排序。不过 insertion sort 是正确的。我们从一个空列表开始，然后将元素一个一个插入到正确的位置：

myMergeSort [2, 1, 4, 3] == 
foldl merge [] [[2], [1], [4], [3]] ==
((([] `merge` [2]) `merge` [1]) `merge` [4]) `merge` [3] == 
(([2] `merge` [1]) `merge` [4]) `merge` [3]
([1, 2] `merge` [4]) `merge` [3] == 
[1, 2, 4] `merge` [3] == 
[1, 2, 3, 4]

由于每次插入都需要线性时间，所以整个排序是二次的。

mergeSortOfficial 在技术上是正确的，但效率低下。 length 需要线性时间，并且在每个递归级别调用列表的总长度。 take 和 drop 也是线性的。总体复杂度仍然是最优的 n * log n，但是我们运行几个不必要的圆圈。

如果我们坚持自上而下的合并，我们可以更好地将列表拆分为具有偶数索引的元素列表和另一个具有奇数索引的元素列表。拆分仍然是线性的，但它只是一次遍历而不是两次（length 然后 take / drop 在 official 排序中）。

split :: [a] -> ([a], [a])
split = go [] [] where
  go as bs []     = (as, bs)
  go as bs (x:xs) = go (x:bs) as xs

mergeSortOfficial :: [Int] -> [Int]
mergeSortOfficial [] = []
mergeSortOfficial (x : []) = [x]
mergeSortOfficial xs = 
  let (as, bs) = split xs in
    merge (mergeSortOfficial as) (mergeSortOfficial bs)

正如 WillNess 在评论中指出的那样，上面的 split 产生了不稳定的排序。我们可以使用稳定的替代方案：

import Control.Arrow

stableSplit :: [a] -> ([a], [a])
stableSplit xs = go xs xs where
    go (x:xs) (_:_:ys) = first (x:) (go xs ys)
    go xs     ys       = ([], xs)

最好的方法可能是进行自下而上的合并。这是 Data.List 中的 sort 所采用的方法。这里我们合并连续的列表对，直到只剩下一个列表：

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort xs = mergeAll (map (:[]) xs) where
    mergePairs (x:y:ys) = merge x y : mergePairs ys
    mergePairs xs       = xs

    mergeAll [xs] = xs
    mergeAll xs   = mergeAll (mergePairs xs)

Data.List.sort 的工作原理与上面大致相同，只是它从在输入中查找降序和升序运行开始，而不是仅仅从元素创建单例列表。

Answer 2

不，那不是 mergeSort。这就是 insertionSort，它与 bubbleSort 本质上是相同的算法，具体取决于您如何看待它。在每一步，一个单例列表 merged 具有到目前为止累积的有序列表，因此，实际上，插入了该单例的元素。

正如其他评论者已经观察到的那样，要获得 mergeSort（尤其是它的效率），有必要将问题重复划分为大致相等的部分（而不是 "one element" 和 "the rest"）。 "official" 解决方案提供了一种相当笨拙的方法来做到这一点。我很喜欢

foldr (\ x (ys, zs) -> (x : zs, ys)) ([], [])

作为将列表一分为二的方法，不是在中间，而是在偶数和奇数位置的元素。

如果像我一样，您喜欢在可以看到的地方预先设置结构，则可以将有序列表设为 Monoid。

import Data.Monoid
import Data.Foldable
import Control.Newtype

newtype Merge x = Merge {merged :: [x]}
instance Newtype (Merge x) [x] where
  pack = Merge
  unpack = merged

instance Ord x => Monoid (Merge x) where
  mempty = Merge []
  mappend (Merge xs) (Merge ys) = Merge (merge xs ys) where
    -- merge is as you defined it

现在你有了插入排序

ala' Merge foldMap (:[]) :: [x] -> [x]

获得mergeSort分而治之结构的一种方法是使它成为一种数据结构：二叉树。

data Tree x = None | One x | Node (Tree x) (Tree x) deriving Foldable

我没有在这里强制执行平衡不变量，但我可以。重点是和之前一样的操作还有另外一个类型

ala' Merge foldMap (:[]) :: Tree x -> [x]

它合并了从树状排列的元素中收集的列表。要获得上述安排，请思考 "what's cons for Tree?" 并确保通过我在上述 "dividing" 操作中使用的相同类型的曲折来保持平衡。

twistin :: x -> Tree x -> Tree x   -- a very cons-like type
twistin x None        = One x
twistin x (One y)     = Node (One x) (One y)
twistin x (Node l r)  = Node (twistin x r) l

现在您通过构建二叉树然后合并它来进行合并排序。

mergeSort :: Ord x => [x] -> [x]
mergeSort = ala' Merge foldMap (:[]) . foldr twistin None

当然，引入中间数据结构有猎奇的价值，但你可以很容易地把它剪下来，得到类似的东西

mergeSort :: Ord x => [x] -> [x]
mergeSort []   = []
mergeSort [x]  = [x]
mergeSort xs   = merge (mergeSort ys) (mergeSort zs) where
  (ys, zs) = foldr (\ x (ys, zs) -> (x : zs, ys)) ([], []) xs

这里的树已经成为程序的递归结构。

这是 Haskell 中正确实施的合并排序吗？

Is this a correctly implemented mergesort in Haskell?

sorting

algorithm

mergesort

haskell

functional-programming