algorithm - Sort a single linked list

Question

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.

Thanks!

Answer 1

Mergesorting involves just a few simple steps:

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

2. Split the list in half. Mergesort both parts.

3. 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.

4. Return merged list.

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

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