// Port of libc++'s std::sort (LLVM 21, __algorithm/sort.h), Apache 2.0 with
// LLVM Exceptions; see NOTICE. Ties in Clipper2's intersection list must come
// out in the order the C++ library gives them.
///|
fn[T] swap_at(a : Array[T], i : Int32, j : Int32) -> Unit {
let t = a[i]
a[i] = a[j]
a[j] = t
}
///|
fn[T] sort3(
a : Array[T],
x : Int32,
y : Int32,
z : Int32,
c : (T, T) -> Bool,
) -> Unit {
if !c(a[y], a[x]) {
if !c(a[z], a[y]) {
return
}
swap_at(a, y, z)
if c(a[y], a[x]) {
swap_at(a, x, y)
}
return
}
if c(a[z], a[y]) {
swap_at(a, x, z)
return
}
swap_at(a, x, y)
if c(a[z], a[y]) {
swap_at(a, y, z)
}
}
///|
fn[T] sort4(
a : Array[T],
x1 : Int32,
x2 : Int32,
x3 : Int32,
x4 : Int32,
c : (T, T) -> Bool,
) -> Unit {
sort3(a, x1, x2, x3, c)
if c(a[x4], a[x3]) {
swap_at(a, x3, x4)
if c(a[x3], a[x2]) {
swap_at(a, x2, x3)
if c(a[x2], a[x1]) {
swap_at(a, x1, x2)
}
}
}
}
///|
fn[T] sort5(
a : Array[T],
x1 : Int32,
x2 : Int32,
x3 : Int32,
x4 : Int32,
x5 : Int32,
c : (T, T) -> Bool,
) -> Unit {
sort4(a, x1, x2, x3, x4, c)
if c(a[x5], a[x4]) {
swap_at(a, x4, x5)
if c(a[x4], a[x3]) {
swap_at(a, x3, x4)
if c(a[x3], a[x2]) {
swap_at(a, x2, x3)
if c(a[x2], a[x1]) {
swap_at(a, x1, x2)
}
}
}
}
}
///|
fn[T] insertion_sort(
a : Array[T],
first : Int32,
last : Int32,
c : (T, T) -> Bool,
) -> Unit {
if first == last {
return
}
for i in (first + 1).. Bool,
) -> Unit {
if first == last {
return
}
for i in (first + 1).. Bool,
) -> Bool {
match last - first {
0 | 1 => return true
2 => {
if c(a[last - 1], a[first]) {
swap_at(a, first, last - 1)
}
return true
}
3 => {
sort3(a, first, first + 1, last - 1, c)
return true
}
4 => {
sort4(a, first, first + 1, first + 2, last - 1, c)
return true
}
5 => {
sort5(a, first, first + 1, first + 2, first + 3, last - 1, c)
return true
}
_ => ()
}
let mut j = first + 2
sort3(a, first, first + 1, j, c)
let mut count = 0
let mut i = j + 1
while i != last {
if c(a[i], a[j]) {
let t = a[i]
let mut k = j
j = i
while true {
a[j] = a[k]
j = k
if j == first {
break
}
k -= 1
if !c(t, a[k]) {
break
}
}
a[j] = t
count += 1
if count == 8 {
return i + 1 == last
}
}
j = i
i += 1
}
true
}
///|
/// Partitions around the pivot at `first`, equal elements to its right: the
/// pivot's place and whether the range was already partitioned.
fn[T] partition_with_equals_on_right(
a : Array[T],
first : Int32,
last : Int32,
c : (T, T) -> Bool,
) -> (Int32, Bool) {
let begin = first
let pivot = a[first]
let mut first = first
let mut last = last
while true {
first += 1
if !c(a[first], pivot) {
break
}
}
if begin == first - 1 {
while first < last {
last -= 1
if c(a[last], pivot) {
break
}
}
} else {
while true {
last -= 1
if c(a[last], pivot) {
break
}
}
}
let already_partitioned = first >= last
while first < last {
swap_at(a, first, last)
while true {
first += 1
if !c(a[first], pivot) {
break
}
}
while true {
last -= 1
if c(a[last], pivot) {
break
}
}
}
let pivot_pos = first - 1
if begin != pivot_pos {
a[begin] = a[pivot_pos]
}
a[pivot_pos] = pivot
(pivot_pos, already_partitioned)
}
///|
/// Partitions around the pivot at `first`, equal elements to its left: the
/// start of the elements greater than the pivot.
fn[T] partition_with_equals_on_left(
a : Array[T],
first : Int32,
last : Int32,
c : (T, T) -> Bool,
) -> Int32 {
let begin = first
let pivot = a[first]
let mut first = first
let mut last = last
if c(pivot, a[last - 1]) {
while true {
first += 1
if c(pivot, a[first]) {
break
}
}
} else {
first += 1
while first < last && !c(pivot, a[first]) {
first += 1
}
}
if first < last {
while true {
last -= 1
if !c(pivot, a[last]) {
break
}
}
}
while first < last {
swap_at(a, first, last)
while true {
first += 1
if c(pivot, a[first]) {
break
}
}
while true {
last -= 1
if !c(pivot, a[last]) {
break
}
}
}
let pivot_pos = first - 1
if begin != pivot_pos {
a[begin] = a[pivot_pos]
}
a[pivot_pos] = pivot
first
}
///|
fn[T] introsort(
a : Array[T],
first : Int32,
last : Int32,
c : (T, T) -> Bool,
depth : Int32,
leftmost : Bool,
) -> Unit {
let mut first = first
let mut last = last
let mut depth = depth
let mut leftmost = leftmost
while true {
let len = last - first
match len {
0 | 1 => return
2 => {
if c(a[last - 1], a[first]) {
swap_at(a, first, last - 1)
}
return
}
3 => {
sort3(a, first, first + 1, last - 1, c)
return
}
4 => {
sort4(a, first, first + 1, first + 2, last - 1, c)
return
}
5 => {
sort5(a, first, first + 1, first + 2, first + 3, last - 1, c)
return
}
_ => ()
}
if len < 24 {
if leftmost {
insertion_sort(a, first, last, c)
} else {
insertion_sort_unguarded(a, first, last, c)
}
return
}
if depth == 0 {
// libc++ falls back to heap sort here (only past 2 log2(n) levels).
let part = a[first:last].to_owned()
stable_sort(part, c)
for i, v in part {
a[first + i] = v
}
return
}
depth -= 1
let half = len / 2
if len > 128 {
sort3(a, first, first + half, last - 1, c)
sort3(a, first + 1, first + (half - 1), last - 2, c)
sort3(a, first + 2, first + (half + 1), last - 3, c)
sort3(a, first + (half - 1), first + half, first + (half + 1), c)
swap_at(a, first, first + half)
} else {
sort3(a, first + half, first, last - 1, c)
}
if !leftmost && !c(a[first - 1], a[first]) {
first = partition_with_equals_on_left(a, first, last, c)
continue
}
let (i, partitioned) = partition_with_equals_on_right(a, first, last, c)
if partitioned {
let fs = insertion_sort_incomplete(a, first, i, c)
if insertion_sort_incomplete(a, i + 1, last, c) {
if fs {
return
}
last = i
continue
} else if fs {
first = i + 1
continue
}
}
introsort(a, first, i, c, depth, leftmost)
leftmost = false
first = i + 1
}
}
///|
/// Sorts `a` by `less` as libc++'s std::sort does (not stable).
fn[T] libcxx_sort(a : Array[T], less : (T, T) -> Bool) -> Unit {
let n = a.length()
if n < 2 {
return
}
let mut log2 = 0
while 1 << (log2 + 1) <= n {
log2 += 1
}
introsort(a, 0, n, less, 2 * log2, true)
}