Implementation of dual-pivot quicksort. It operates in-place on the provided Seq, using a small amount of additional memory. The nature of the element-realation is expressed via the supplied comparator.
(The following is paraphrased from Wikipedia.)
Quicksort is a common implementation of a sort algorithm which can sort items of any type for which a "less-than" relation (formally, a total order) is defined.
On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Multi-pivot implementations (of which dual-pivot is one) make efficient use of modern processor caches.
The following takes an reverse-alphabetical array of Strings ("third", "second", "first"), and sorts it in place alphabetically using the default String Comparator.
It outputs:
first second third
use "collections"
actor Main
new create(env:Env) =>
let array = [ "third"; "second"; "first" ]
let sorted_array = Sort[Array[String], String](array)
for e in sorted_array.values() do
env.out.print(e) // prints "first \n second \n third"
end
```
```pony
primitive val Sort[A: Seq[B] ref, B: Comparable[B] #read]
new val create() : Sort[A, B] val^
Sort the given seq.
fun box apply( a: A) : A^
fun box eq( that: Sort[A, B] val) : Bool val
fun box ne( that: Sort[A, B] val) : Bool val
fun box _sort( a: A, lo: ISize val, hi: ISize val) : None val ?
fun box _swap( a: A, i: ISize val, j: ISize val) : None val ?
© 2016-2018, The Pony Developers
© 2014-2015, Causality Ltd.
Licensed under the BSD 2-Clause License.
https://stdlib.ponylang.io/collections-Sort