你会如何排序单链表。 （这里的问题是单一属性+使用链表的排序不是一个数组更难） 我喜欢看伪code ..

How would you sort a single linked list. (the problem here is the single property + using LinkedList for sorting is harder than an array) I had like to see a pseudo code..

试着让它尽可能高效的时间和空间。

try to make it efficient as possible for both time and space.

谢谢！

推荐答案

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

Mergesorting involves just a few simple steps:

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

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