Mergesorting只涉及几个简单的步骤：

Mergesorting involves just a few simple steps:

1. 检查列表为空或有一个单一的元素。如果是这样，则返回列表不变。

1. Check if the list is empty or has a single element. If so, return the list unchanged.

拆分列表中的一半。归并两个部分。

Split the list in half. Mergesort both parts.

通过反复采取更小的元素了两份名单的合并列表。由于部分名单已经排序，这是在看两个列表中的第一要素，并挑选小问题而已。

Merge the lists by repeatedly taking the smaller element out of both lists. Since the part lists are already sorted, this is just a matter of looking at the first elements in both lists and picking the smaller.

返回合并列表。

这样一来，你会得到一个链接列表进行排序，以最小的元素首。

As a result you will get a linked list sorted in order of smallest element first.

在Haskell code例如：

Code example in Haskell:

import Data.List(splitAt)

--Mergesorts a list by smallest element first.
sort :: Ord a => [a] -> [a]
sort = sortBy (<)

--Generic sort that can sort in any order.
sortBy :: (a -> a -> Bool) -> [a] -> [a]
sortBy _ [] = []
sortBy _ [x] = [x]
sortBy f xs = merge f (sortBy f first) (sortBy f second)
    where
        (first,second) = split xs

--Splits a list in half.
split :: [a] -> ([a],[a])
split xs = splitAt (halfLength xs) xs

--Returns a lists length divided by two as a whole number (rounded).
halfLength :: [a] -> Int
halfLength = round . (/2) . fromIntegral . length

--Merges two lists in the provided order.
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge _ [] [] = []
merge _ [] (y:ys) = y:ys
merge _ (x:xs) [] = x:xs
merge f (x:xs) (y:ys) =
    if f x y
        then x : merge f xs (y:ys)
        else y : merge f (x:xs) ys