Abstract

Bitonic merge sort.

Runs in O(n log²(n)) work and O(log²(n)) span. Internally pads the array to the next power of two, so a poor fit for some array sizes.

Synopsis

val merge_sort [n] 't : (<=: t -> t -> bool) -> (xs: [n]t) -> *[n]t
val merge_sort_by_key [n] 't 'k : (key: t -> k) -> (<=: k -> k -> bool) -> (xs: [n]t) -> [n]t

Description

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

Sort an array in increasing order.

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

Like merge_sort, but sort based on key function.