Data-parallel implementation of quicksort.
- ↑val qsort [n] 't: (<=: t -> t -> bool) -> (xs: [n]t) -> [n]t
Quicksort. Given a comparison function (<=) and an array of elements,
qsort (<=) xsreturns an array with the elements in
xssorted 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).