Abstract
Data-parallel implementation of quicksort. Note that this quicksort, while parallel, is quite slow. In almost all cases you should use radix- or merge sort instead.
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 inxs
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.