sort.oak

← Standard library See on GitHub ↗

// libsort implements efficient list sorting algorithms

{
	default: default
	identity: id
	map: map
	clone: clone
} := import('std')

// sort! sorts items in the list `xs` by each item's `pred` value, using the
// Hoare partitioning strategy. If `pred` is not given, each item is sorted by
// its own value. It mutates the original list for efficiency. If mutation is
// not desired, use sort below.
fn sort!(xs, pred) {
	pred := default(pred, id)

	vpred := xs |> map(pred)

	fn partition(xs, lo, hi) {
		pivot := vpred.(lo)
		fn lsub(i) if vpred.(i) < pivot {
			true -> lsub(i + 1)
			_ -> i
		}
		fn rsub(j) if vpred.(j) > pivot {
			true -> rsub(j - 1)
			_ -> j
		}
		fn sub(i, j) {
			i := lsub(i)
			j := rsub(j)
			if i < j {
				false -> j
				_ -> {
					tmp := xs.(i)
					tmpPred := vpred.(i)
					xs.(i) := xs.(j)
					xs.(j) := tmp
					vpred.(i) := vpred.(j)
					vpred.(j) := tmpPred

					sub(i + 1, j - 1)
				}
			}
		}
		sub(lo, hi)
	}

	fn quicksort(xs, lo, hi) if len(xs) {
		0, 1 -> xs
		_ -> if lo < hi {
			false -> xs
			_ -> {
				p := partition(xs, lo, hi)
				quicksort(xs, lo, p)
				quicksort(xs, p + 1, hi)
			}
		}
	}

	quicksort(xs, 0, len(xs) - 1)
}

// sort returns a copy of `xs` that is sorted by `pred`, or by each item's
// value if `pred` is not given. If the performance cost of a copy is not
// desirable, use sort!.
fn sort(xs, pred) xs |> clone() |> sort!(pred)