# Haskell Merge Sort

September 11th, 2017

Image by Kelsie DiPerna

One of the things I love about Haskell is its expressiveness. What is
full of process in an imperative language is often a simple
description in Haskell. As an example, consider one possible merge sort
implementation.

## merge

The

merge

function merges two sorted lists. The heads of each list
are compared, and the smaller element is prepended to a merge on the remaining
lists. When one list is empty, the other list holds the largest elements in
sorted order, and we can append these.

The resulting list is sorted regardless of the length of the input lists.

If one list is empty, the other list is immediately returned. If both lists are
empty, an empty list is returned.

## halve

The

halve

function splits a list into two halves with the

take

and

drop

functions.

A couple of examples to demonstrate halving.

## msort

The

msort

function implements merge sort by recursively halving a list and
merging the sorted lists as they return. The merge starts by assembling
zero- and one-element lists returned from the

halve

base cases.

The

msort

function can be tested on base cases and simple lists of even and
odd length.

In terms of speed, a good low-level implementation of merge sort will outperform
the Haskell version. But Haskell provides another benefit.

## Type Inference

Notice that our merge sort implementation has stayed general by only using type
variables. This means we can sort

Char

,

String

,

Float

, and any other type
in the

Ord

typeclass.

Alternative representations can also be inferred. The largest 64-bit integer is
9,223,372,036,854,775,807. What happens if we want to sort larger values?
Haskell will infer that we must be working with the arbitrary precision

Integer

type instead of the bounded

Int

type.

## Conclusion

Expressiveness and type inference are a couple of the benefits of a Haskell
merge sort. The benefits should be weighed against the performance cost. A
Haskell merge sort implementation is probably not the best choice in some cases,
but it is a nice choice when you can make it.