# Insertion sort (Haskell)

### From LiteratePrograms

**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(<=)[10]))= 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[]=[10]

and we are left with

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

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[10]= 3:10:[]=[3,10]

However, 5 is not <= 3, so

insert(<=)5[3,10]= 3:(insert(<=)5[10])= 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"]

Download code |