# Insertion sort (Haskell)

Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

This is a simple example of the insertion sort sorting algorithm, written in Haskell. This implementation will sort an arbitrary length list, using a user-defined sorting predicate (such as <= for a standard numerical sort).

## Implementation

Insertion sort takes a predicate that compares two values of the same type. It returns a function that takes a list of that comparable type and returns a sorted version of the list.

```<<insertion_sort.hs>>=
insertion_sort :: (a -> a -> Bool) -> [a] -> [a]
```

The empty list can already be considered sorted.

```<<insertion_sort.hs>>=
insertion_sort pred []     = []
```

In the case of non-empty lists, we recursively `insert` the first element of the list into an already insertion-sorted version of the rest of the list.

```<<insertion_sort.hs>>=
insertion_sort pred (x:xs) = insert pred x (insertion_sort pred xs)
```

So, for example

```insertion_sort (<=) [5,3,10] = insert (<=) 5 (insertion_sort (<=) [3,10])
= insert (<=) 5 (insert (<=) 3 (insertion_sort (<=) ))
= insert (<=) 5 (insert (<=) 3 (insert (<=) 10 (insertion_sort (<=) [])))
```

Which reduces to

```                             = insert (<=) 5 (insert (<=) 3 (insert (<=) 10 []))
```

since

```insertion_sort pred [] = []
```

To further evaluate the insertion sort function, we need to understand how the `insert` function works.

### `insert`

The `insert` function takes a predicate that compares two values of the same type, an element of the comparable type, and a list of already sorted elements. It returns another sorted list, with the insertion element correctly positioned.

```<<insertion_sort.hs>>=
insert :: (a -> a -> Bool) -> a -> [a] -> [a]
```

An element being inserted into an empty list requires no comparisons, and can simply be returned as a list.

```<<insertion_sort.hs>>=
insert pred x [] = [x]
```

So, from our previous example we can determine that

```insert (<=) 10 [] = 
```

and we are left with

```insertion_sort (<=) [5,3,10] = insert (<=) 5 (insert (<=) 3 )
```

For non-empty lists, the element being inserted, `x` is compared to the first element of the list, `y`, using the predicate `pred`. If the predicate evaluates to `True` then `x` is assumed to be lower in the ordering than `y`, and is prepended to the sorted list. Otherwise, if the predicate evaluates to false, then `y` is considered lower in the ordering than `x`, and must remain the first element in the list. The element `x` must then be inserted somewhere after `y` in the list.

```<<insertion_sort.hs>>=
insert pred x (y:ys)
| pred x y = (x:y:ys)
| otherwise = y:(insert pred x ys)
```

Continuing with our example, we can see that 3 <= 10, so

```insert (<=) 3  = 3:10:[]
= [3,10]
```

However, 5 is not <= 3, so

```insert (<=) 5 [3,10] = 3:(insert (<=) 5 )
= 3:(5:10:[])
= [3,5,10]
```

As a result

```insertion_sort (<=) [5,3,10] = [3,5,10]
```

and the list is sorted.

## Testing

The insertion sort implementation can easily be tested in an interactive Haskell environment such as Hugs or the Glasgow Haskell Compiler's GHCi. For example, after loading `insertion_sort.hs` into GHCi, typing

```insertion_sort (<=) [1, 5, 6, 4, 3]
```

at the prompt produces the sorted list

```[1,3,4,5,6]
```

Since the insertion sort implementation is generic, we can also sort non-numeric lists:

```*Main> insertion_sort (<=) ["bob","alice","zoe","barry"]
["alice","barry","bob","zoe"]
```