structure Quicksort

type 'a seq = 'a Seq.t

These functions use the Seq representation of sequences.

val sortInPlace: ('a * 'a -> order) -> 'a seq -> unit

sortInPlace cmp s sorts s and writes the result in-place. Not guaranteed to be a stable sort (see StableSort).

Work: O(|s|log|s|)

Span: polylog|s|

The algorithm is Vladimir Yaroslavskiy's dual-pivot quicksort. Implementation here provided by Guy Blelloch.

val sort: ('a * 'a -> order) -> 'a seq -> 'a seq

A purely functional version. The input is not modified; instead, a fresh array is produced as output.