## 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.