Abstract

Data-parallel implementation of quicksort.

Synopsis

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

Description

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

Quicksort. Given a comparison function (<=) and an array of elements, qsort (<=) xs returns an array with the elements in xs sorted according to <=. The algorithm has best case work complexity O(n) (when all elements are identical), worst case work complexity O(n^2), and an average case work complexity of O(n log n). It has best depth complexity O(1), worst depth complexity O(n) and average depth complexity O(log n).

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

Like qsort, but sort based on key function.