Skip to main content

zero_client/
sort.rs

1//! `Array.prototype.sort` as V8 implements it.
2//!
3//! Some comparators the client ports are not consistent (the AST condition
4//! comparator orders subqueries before conjunctions from both sides), so the
5//! result depends on the exact sequence of comparisons. V8's TimSort, for
6//! arrays shorter than its minimum run of 64, finds the leading run
7//! (reversing it if strictly descending) and binary-insertion-sorts the rest;
8//! that is reproduced here exactly. Longer arrays use the same insertion
9//! sort, which matches V8 for consistent comparators (it is stable).
10
11use std::cmp::Ordering;
12
13pub fn sort<T>(a: &mut [T], mut cmp: impl FnMut(&T, &T) -> Ordering) {
14    let n = a.len();
15    if n < 2 {
16        return;
17    }
18    // CountAndMakeRun
19    let descending = cmp(&a[1], &a[0]).is_lt();
20    let mut run = 2;
21    while run < n {
22        let order = cmp(&a[run], &a[run - 1]);
23        if if descending {
24            order.is_ge()
25        } else {
26            order.is_lt()
27        } {
28            break;
29        }
30        run += 1;
31    }
32    if descending {
33        a[..run].reverse();
34    }
35    // BinaryInsertionSort(low = 0, startArg = run, high = n)
36    for start in run..n {
37        let (mut left, mut right) = (0, start);
38        while left < right {
39            let mid = left + ((right - left) >> 1);
40            if cmp(&a[start], &a[mid]).is_lt() {
41                right = mid;
42            } else {
43                left = mid + 1;
44            }
45        }
46        a[left..=start].rotate_right(1);
47    }
48}