How to implement the insertion sort in Haskell

Overview

Haskell is a functional programming language. The functional programming paradigm focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions. Let’s see how to implement one of the most popular sorting algorithms, the insertion sort, in Haskell.

Algorithm

The basic idea behind insertion sort is that we repeatedly place each unsorted element in its correct place so that we end up with a sorted list.

We can divide the algorithm into two parts:

1. Insert a new element in a sorted list in its correct place.
2. Repeate the above process on each element of the input list recursively to get the final sorted list.

Example

Let’s translate the above algorithm into a Haskell program:

Explanation

The insert_sorted function

The insert_sorted function inserts a new element in a sorted list in its correct place.

• Line 1: The type annotation insert_sorted :: [Int] -> Int -> [Int] shows that our function takes a list of integers, an integer element that needs to be inserted, and returns the resultant list.
• Lines 2–3: Next, we have the function definition that shows that our function takes a list, an integer element v, followed by a case expression that implements the recursive formulation of the problem.
• Line 4: x:xs in the case statement is a syntax in Haskell that destructures a list into its head element and the remainder list.
• Line 5: We compare the input element with the head of the list. If the input element is greater, we must traverse the remaining list. Therefore, we return the list with the head of the original list concatenated with the result of the recursive call to the insert_sorted function which is now passed the remainder of the list xs. In the second case statement, we check if the input element is less than the head element, and then place the input element at the beginning of the list.

The insertion_sort function

Let’s put all the pieces together.

• Line 9: The first case statement handles the base scenario. If an empty list is passed as input, there is nothing to sort, and we return an empty list.
• Line 10–11: For the general case, we recursively call the insertion_sort function. We pass it xs, the list with its head removed. We can assume that our function correctly sorts the list xs. The insert_sorted function determines the correct place of the unsorted head element in the sorted list returned by the recursive call. We return the list returned by the insert_sorted function, which correctly places the unsorted head element, and we end up with a sorted list.