Sorting algorithms in Haskell

Saturday, Dec 26, 2020
Functional Haskell

In earlier posts, I looked at construction of merge sort, quick sort and insertion sort algorithms in an imperative language. Besides the fact that the overall code is longer in imperative, it would take me even longer to read and comprehend the logic. Code readability is another area where functional languages shine. Let's see how these algorithms are written in Haskell.

Merge Sort

Here we divide the problem into two parts:

instead of sorting the entire list in one go, divide the list into two and sort those
merge two lists that are already sorted

merge :: Ord a => [a] -> [a] -> [a]
merge [] l = l
merge l [] = l
merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort l = merge (msort left) (msort right)
  where
    left = take half l
    right = drop half l
    half = (length l) `div` 2

Quick Sort

Here, we choose the first element of the list as pivot. Then we split the tail into two lists - a list with elements that are smaller than or equal to pivot and a list with elements that are larger than the pivot. We sort these two lists using quick sort and append the smaller element list to the left side of pivot and larger element list to the right side of pivot.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort [x] = [x]
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [s | s <- xs, s <= x]
    larger = [l | l <- xs, l > x]

Insertion Sort

Here again, we divide the problem into two parts:

sort the tail of list using insertion sort
insert the head at the appropriate position of the sorted tail such that the resulting list is still sorted.

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
                | otherwise = y : insert x ys

isort :: Ord a => [a] -> [a]
isort [] = []
isort [x] = [x]
isort (x:xs) = insert x (isort xs)

And..

Besides the clear intention of what the algorithm is doing, the code is also beautiful. Furthermore, note that all algorithms are polymorphic - not only they work with number of different kinds, they work with any type that is an instance of Ord class - Char, String, Bool and lists, tuples containing these types! This is indeed powerful. I am liking functional languages!

*Main> isort [True, False]
[False,True]
*Main> msort ["hello", "aloha"]
["aloha","hello"]
*Main> qsort "hello"
"ehllo"
*Main> msort [6,5..1]
[1,2,3,4,5,6]