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.