## Abstract

A sequential implementation of insertion sort.

## Synopsis

val insertion_sort | [n] 't : | (<=: t -> t -> bool) -> (xs: [n]t) -> *[n]t |

val insertion_sort_by_key | [n] 't 'k : | (key: t -> k) -> (<=: k -> k -> bool) -> (xs: [n]t) -> [n]t |

## Description

- ↑val insertion_sort [n] 't: (<=: t -> t -> bool) -> (xs: [n]t) -> *[n]t
Insertion sort. Runs with

*O(n^2)*work and*O(n^2)*depth.- ↑val insertion_sort_by_key [n] 't 'k: (key: t -> k) -> (<=: k -> k -> bool) -> (xs: [n]t) -> [n]t
Like

`insertion_sort`

, but sort based on key function.