Это правильно реализованная сортировка слиянием в Haskell?

myMergeSort не является правильной сортировкой слиянием. Однако это правильная сортировка вставками. Мы начинаем с пустого списка, затем вставляем элементы один за другим в правильную позицию:

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)

Как отметил УиллНесс в комментариях, приведенный выше 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)

Лучший способ, вероятно, сделать слияние снизу вверх. Это подход sort в Data.List занимает. Здесь мы объединяем последовательные пары списков, пока не останется только один список:

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 работает в основном так же, как и выше, за исключением того, что он начинается с поиска нисходящих и восходящих последовательностей во входных данных, а не просто создания одноэлементных списков из элементов.

Нет, это не сортировка слиянием. Это insertionSort, который по сути является тем же алгоритмом, что и bubbleSort, в зависимости от того, как вы на него смотрите. На каждом шаге список синглтона равен merged накопленному упорядоченному списку на данный момент, поэтому фактически вставляется элемент этого синглтона.

Как уже заметили другие комментаторы, чтобы получить mergeSort (и, в частности, его эффективность), необходимо неоднократно делить задачу на примерно равные части (а не на «один элемент» и «остальные») . «Официальное» решение дает довольно неуклюжий способ сделать это. мне очень нравится

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]

который объединяет списки, собранные из древовидного расположения элементов. Чтобы получить указанные договоренности, подумайте "какие минусы для Tree?" и убедитесь, что вы сохраняете равновесие, используя ту же извилистость, которую я использовал в приведенной выше операции «разделения».

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 путем построения двоичного дерева, а затем его слияния.

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

где дерево стало рекурсивной структурой программы.