Skip to content

Sort[A: Seq[B] ref, B: Comparable[B] #read]

[Source]

Implementation of introsort: dual-pivot quicksort with a heapsort fallback when recursion depth exceeds O(log n). Sorts in-place, using a small amount of additional memory. Elements must satisfy the Comparable interface.

Dual-pivot quicksort partitions around two pivots into three regions, making efficient use of modern processor caches. When the quicksort partitioning degenerates (e.g. on already-sorted, reverse-sorted, or all-equal input), the affected subarray is heapsorted instead, keeping the worst case at O(n log n).

Example program

The following sorts a reverse-alphabetical array of Strings in place.

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

primitive val Sort[A: Seq[B] ref, B: Comparable[B] #read]

Constructors

create

[Source]

new val create()
: Sort[A, B] val^

Returns

Public Functions

apply

[Source]

Sort the given seq.

fun box apply(
  a: A)
: A^

Parameters

  • a: A

Returns

  • A^

eq

[Source]

fun box eq(
  that: Sort[A, B] val)
: Bool val

Parameters

  • that: Sort[A, B] val

Returns

ne

[Source]

fun box ne(
  that: Sort[A, B] val)
: Bool val

Parameters

  • that: Sort[A, B] val

Returns