xref: /arkcompiler/runtime_core/static_core/plugins/ets/stdlib/std/core/BuiltinArraySort.sts

/**
 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package std.core;

// NOTE: autogenerated file

function bubbleSort(arr: boolean[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (((arr[i + 1]) ? 1 : 0) < ((arr[i]) ? 1 : 0)) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: boolean[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (((tmp) ? 1 : 0) < ((arr[pos - 1]) ? 1 : 0)) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (((tmp) ? 1 : 0) < ((arr[startIndex]) ? 1 : 0)) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (((tmp) ? 1 : 0) < ((arr[pos - 1]) ? 1 : 0)) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: boolean[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    countSortBools(arr, startIndex, endIndex)
}

function bubbleSort(arr: boolean[], startIndex: int, endIndex: int, mustPrecede: (lhs: boolean, rhs: boolean) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: boolean[], startIndex: int, endIndex: int, mustPrecede: (lhs: boolean, rhs: boolean) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: boolean[], startIndex: int, endIndex: int, mustPrecede: (lhs: boolean, rhs: boolean) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    if (mustPrecede(false, true)) {
        countSortBools(arr, startIndex, endIndex)
    } else {
        countSortBoolsInv(arr, startIndex, endIndex)
    }
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: boolean[], mustPrecede: (lhs: boolean, rhs: boolean) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: boolean[], startIndex: int, mustPrecede: (lhs: boolean, rhs: boolean) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

function countSortTruthCnt(arr: boolean[], startIndex: int, endIndex: int): int {
    let truthCnt = 0
    for (let i = startIndex; i < endIndex; i++) {
        if (arr[i]) {
            truthCnt++
        }
    }
    return truthCnt
}

function countSortBools(arr: boolean[], startIndex: int, endIndex: int): void {
    const truthCnt = countSortTruthCnt(arr, startIndex, endIndex)
    for (let i = startIndex; i < endIndex - truthCnt; i++) {
            arr[i] = false
        }
    for (let i = 0; i < truthCnt; i++) {
        arr[endIndex - truthCnt + i] = true
    }
}
function countSortBoolsInv(arr: boolean[], startIndex: int, endIndex: int): void {
    const truthCnt = countSortTruthCnt(arr, startIndex, endIndex)
    for (let i = 0; i < truthCnt; i++) {
        arr[startIndex + i] = true
    }
    for (let i = startIndex + truthCnt; i < endIndex; i++) {
        arr[i] = false
    }
}

export function sort(arr: boolean[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDataboolean {
    name: string
    arr: boolean[]

    constructor(name: string, arr: boolean[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: boolean[]): boolean[] {
    let c = new boolean[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_boolean(l: boolean, r: boolean): boolean {
    return ((l) ? 1 : 0) < ((r) ? 1 : 0)
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_boolean(l: boolean, r: boolean): boolean {
    return ((r) ? 1 : 0) < ((l) ? 1 : 0)
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: boolean[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: boolean[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDataboolean>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDataboolean("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDataboolean("insertion", insertion))

        const bcnt = test_sortCopy(arr)
        countSortBools(bcnt, 0, bcnt.length)
        sorts.push(new test_SortDataboolean("bools cnt()", bcnt))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDataboolean("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for boolean')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_boolean`
    if (true) {
        const sorts = new Array<test_SortDataboolean>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_boolean)
        sorts.push(new test_SortDataboolean("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_boolean)
        sorts.push(new test_SortDataboolean("insertion", insertion))

        const bcnt = test_sortCopy(arr)
        countSortBools(bcnt, 0, bcnt.length)
        sorts.push(new test_SortDataboolean("bools cnt()", bcnt))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_boolean)
        sorts.push(new test_SortDataboolean("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_boolean are not equal: " + sort0.name + ' ' + sortS.name + ' for boolean')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_boolean`
    if (true) {
        const sorts = new Array<test_SortDataboolean>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_boolean)
        sorts.push(new test_SortDataboolean("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_boolean)
        sorts.push(new test_SortDataboolean("insertion", insertion))

        const bcnt = test_sortCopy(arr)
        countSortBoolsInv(bcnt, 0, bcnt.length)
        sorts.push(new test_SortDataboolean("bools cnt()", bcnt))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_boolean)
        sorts.push(new test_SortDataboolean("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_boolean are not equal: " + sort0.name + ' ' + sortS.name + ' for boolean')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: byte[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: byte[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: byte[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: byte[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: byte[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: byte[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: byte[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: byte[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: byte[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: byte[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: byte[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: byte[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    if (endIndex - startIndex > 1024) {
        countSort(arr, startIndex, endIndex)
    }
    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: byte[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: byte[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: byte[], index1: int, index2: int, index3: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: byte[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: byte[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: byte[], startIndex: int, endIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: byte[], mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: byte[], startIndex: int, mustPrecede: (lhs: byte, rhs: byte) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

function countSort(arr: byte[], startIndex: int, endIndex: int): void {
    const cnts = new int[256]
    for (let i = startIndex; i < endIndex; i++) {
        cnts[arr[i] + 128]++
    }
    let idx = 0
    for (let i = 0; i < 256; i++) {
        for (let j = 0; j < cnts[i]; j++) {
            arr[startIndex + idx++] = (i - 128) as byte
        }
    }
}

export function sort(arr: byte[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatabyte {
    name: string
    arr: byte[]

    constructor(name: string, arr: byte[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: byte[]): byte[] {
    let c = new byte[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_byte(l: byte, r: byte): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_byte(l: byte, r: byte): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: byte[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: byte[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatabyte>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatabyte("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatabyte("insertion", insertion))
        const cnt = test_sortCopy(arr)
        countSort(cnt, 0, cnt.length)
        sorts.push(new test_SortDatabyte("cnt()", cnt))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatabyte("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatabyte("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatabyte("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatabyte("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for byte')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_byte`
    if (true) {
        const sorts = new Array<test_SortDatabyte>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_byte)
        sorts.push(new test_SortDatabyte("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_byte are not equal: " + sort0.name + ' ' + sortS.name + ' for byte')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_byte`
    if (true) {
        const sorts = new Array<test_SortDatabyte>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_byte)
        sorts.push(new test_SortDatabyte("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_byte are not equal: " + sort0.name + ' ' + sortS.name + ' for byte')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: short[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: short[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: short[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: short[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: short[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: short[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: short[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: short[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: short[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: short[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: short[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: short[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: short[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: short[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: short[], index1: int, index2: int, index3: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: short[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: short[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: short[], startIndex: int, endIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: short[], mustPrecede: (lhs: short, rhs: short) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: short[], startIndex: int, mustPrecede: (lhs: short, rhs: short) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: short[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatashort {
    name: string
    arr: short[]

    constructor(name: string, arr: short[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: short[]): short[] {
    let c = new short[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_short(l: short, r: short): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_short(l: short, r: short): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: short[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: short[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatashort>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatashort("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatashort("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatashort("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatashort("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatashort("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatashort("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for short')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_short`
    if (true) {
        const sorts = new Array<test_SortDatashort>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_short)
        sorts.push(new test_SortDatashort("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_short are not equal: " + sort0.name + ' ' + sortS.name + ' for short')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_short`
    if (true) {
        const sorts = new Array<test_SortDatashort>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_short)
        sorts.push(new test_SortDatashort("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_short are not equal: " + sort0.name + ' ' + sortS.name + ' for short')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: int[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: int[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: int[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: int[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: int[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: int[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: int[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: int[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: int[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: int[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: int[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: int[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: int[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: int[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: int[], index1: int, index2: int, index3: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: int[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: int[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: int[], startIndex: int, endIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: int[], mustPrecede: (lhs: int, rhs: int) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: int[], startIndex: int, mustPrecede: (lhs: int, rhs: int) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: int[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDataint {
    name: string
    arr: int[]

    constructor(name: string, arr: int[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: int[]): int[] {
    let c = new int[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_int(l: int, r: int): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_int(l: int, r: int): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: int[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: int[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDataint>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDataint("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDataint("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDataint("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDataint("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDataint("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDataint("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for int')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_int`
    if (true) {
        const sorts = new Array<test_SortDataint>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_int)
        sorts.push(new test_SortDataint("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_int are not equal: " + sort0.name + ' ' + sortS.name + ' for int')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_int`
    if (true) {
        const sorts = new Array<test_SortDataint>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_int)
        sorts.push(new test_SortDataint("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_int are not equal: " + sort0.name + ' ' + sortS.name + ' for int')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: long[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: long[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: long[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: long[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: long[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: long[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: long[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: long[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: long[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: long[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: long[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: long[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: long[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: long[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: long[], index1: int, index2: int, index3: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: long[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: long[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: long[], startIndex: int, endIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: long[], mustPrecede: (lhs: long, rhs: long) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: long[], startIndex: int, mustPrecede: (lhs: long, rhs: long) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: long[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatalong {
    name: string
    arr: long[]

    constructor(name: string, arr: long[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: long[]): long[] {
    let c = new long[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_long(l: long, r: long): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_long(l: long, r: long): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: long[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: long[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatalong>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatalong("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatalong("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatalong("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatalong("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatalong("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatalong("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for long')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_long`
    if (true) {
        const sorts = new Array<test_SortDatalong>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_long)
        sorts.push(new test_SortDatalong("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_long are not equal: " + sort0.name + ' ' + sortS.name + ' for long')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_long`
    if (true) {
        const sorts = new Array<test_SortDatalong>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_long)
        sorts.push(new test_SortDatalong("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_long are not equal: " + sort0.name + ' ' + sortS.name + ' for long')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: float[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: float[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: float[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: float[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: float[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: float[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: float[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: float[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: float[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: float[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: float[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: float[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: float[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: float[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: float[], index1: int, index2: int, index3: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: float[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: float[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: float[], startIndex: int, endIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: float[], mustPrecede: (lhs: float, rhs: float) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: float[], startIndex: int, mustPrecede: (lhs: float, rhs: float) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: float[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatafloat {
    name: string
    arr: float[]

    constructor(name: string, arr: float[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: float[]): float[] {
    let c = new float[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_float(l: float, r: float): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_float(l: float, r: float): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: float[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: float[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatafloat>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatafloat("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatafloat("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatafloat("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatafloat("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatafloat("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatafloat("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for float')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_float`
    if (true) {
        const sorts = new Array<test_SortDatafloat>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_float)
        sorts.push(new test_SortDatafloat("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_float are not equal: " + sort0.name + ' ' + sortS.name + ' for float')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_float`
    if (true) {
        const sorts = new Array<test_SortDatafloat>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_float)
        sorts.push(new test_SortDatafloat("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_float are not equal: " + sort0.name + ' ' + sortS.name + ' for float')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: double[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: double[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: double[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: double[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: double[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: double[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: double[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: double[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: double[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: double[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: double[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: double[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: double[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: double[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: double[], index1: int, index2: int, index3: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: double[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: double[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: double[], startIndex: int, endIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: double[], mustPrecede: (lhs: double, rhs: double) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: double[], startIndex: int, mustPrecede: (lhs: double, rhs: double) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: double[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatadouble {
    name: string
    arr: double[]

    constructor(name: string, arr: double[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: double[]): double[] {
    let c = new double[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_double(l: double, r: double): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_double(l: double, r: double): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: double[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: double[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatadouble>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatadouble("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatadouble("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatadouble("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatadouble("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatadouble("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatadouble("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for double')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_double`
    if (true) {
        const sorts = new Array<test_SortDatadouble>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_double)
        sorts.push(new test_SortDatadouble("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_double are not equal: " + sort0.name + ' ' + sortS.name + ' for double')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_double`
    if (true) {
        const sorts = new Array<test_SortDatadouble>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_double)
        sorts.push(new test_SortDatadouble("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_double are not equal: " + sort0.name + ' ' + sortS.name + ' for double')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: char[], startIndex: int, endIndex: int): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if ((arr[i + 1] < arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: char[], startIndex: int, endIndex: int, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if ((tmp < arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while ((tmp < arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: char[], idxFromStart: int, startIndex: int, heapRoot: int): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!(arr[startIndex + p] < tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: char[], idxFromStart: int, startIndex: int, endIndex: int): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if ((arr[childIndex] < arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot)
}

export function heapSort(arr: char[], startIndex: int, endIndex: int): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: char[], index1: int, index2: int, index3: int): void {
    let swap_idx = index2
    if ((arr[index1] < arr[index2])) {
        if ((arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index3] < arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!(arr[index3] < arr[index1])) {
            return
        }
        if ((arr[index2] < arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: char[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((arr[i] < pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !(arr[j] < pivot)) {
            j--
        }
    } else {
        while (!(arr[j] < pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !(arr[i] < pivot) and (arr[j] < pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while ((arr[++i] < pivot)) {}
        while (!(arr[--j] < pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: char[], startIndex: int, endIndex: int): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while ((pivot < arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !(pivot < arr[i])) {
            i++
        }
    } else {
        while (!(pivot < arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here (pivot < arr[i]) and !(pivot < arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!(pivot < arr[++i])) {}
        while ((pivot < arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: char[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}
function quickSortImpl40(arr: char[], startIndex: int, endIndex: int, maxDepth: int, initIndex: int = startIndex): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex)
            return
        }
        // Here we assume that current interval is not the most left in the sorted range
        if (startIndex != initIndex && arr[startIndex - 1] >= arr[startIndex]) {
            // We call quickSortSplitLeft here to move all elements equal to pivot (and arr[startIndex - 1]) to the left part;
            // after that only the right part needs to be sorted
            // If we always used quickSortSplitLeft instead of quickSortSplit, this would not work well for array
            // with many occurencies of the smallest element
            startIndex = quickSortSplitLeft(arr, startIndex, endIndex) + 1
            continue
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2)
        let p = quickSortSplit(arr, startIndex, endIndex)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, initIndex)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, initIndex)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, initIndex)
}

function quickSort(arr: char[], startIndex: int, endIndex: int): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort(arr: char[], startIndex: int, endIndex: int): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex);
}

function bubbleSort(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: char[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: char[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: char[], index1: int, index2: int, index3: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: char[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: char[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: char[], startIndex: int, endIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: char[], mustPrecede: (lhs: char, rhs: char) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: char[], startIndex: int, mustPrecede: (lhs: char, rhs: char) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}

export function sort(arr: char[], startIndex: int): void {
    sort(arr, startIndex, arr.length)
}

// ======== tests section ========

/** note: used for tests, {@link test_sortAllOn} */
class test_SortDatachar {
    name: string
    arr: char[]

    constructor(name: string, arr: char[]) {
        this.name = name
        this.arr = arr
    }
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortCopy(arr: char[]): char[] {
    let c = new char[arr.length]
    for (let i = 0; i < arr.length; i++) {
        c[i] = arr[i]
    }
    return c
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpFwd_char(l: char, r: char): boolean {
    return l < r
}

/** note: used for tests, {@link test_sortAllOn} */
function test_sortAllOnCmpInv_char(l: char, r: char): boolean {
    return r < l
}

/** note: used for tests, {@link test_sortAllOn} */
function test_printArr(arr: char[], startIndex: int, endIndex: int) {
    for (let i = startIndex; i < endIndex; i++) {
        console.print(arr[i] + ' ')
    }
    console.println('')
}

/**
 * Function used to test sorting in standard library tests.
 * There is only one exported function: `sort`, but for testing
 * we need access to all sub sorts that are used. Hence this part of "tests"
 * is located here. All related entities are prefixed whith `test_` to stand out
 */
export function test_sortAllOn(arr: char[]) {
    // block for comparator ``
    if (true) {
        const sorts = new Array<test_SortDatachar>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length)
        sorts.push(new test_SortDatachar("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length)
        sorts.push(new test_SortDatachar("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length)
        sorts.push(new test_SortDatachar("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length)
        sorts.push(new test_SortDatachar("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length)
        sorts.push(new test_SortDatachar("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort(just)
        sorts.push(new test_SortDatachar("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts are not equal: " + sort0.name + ' ' + sortS.name + ' for char')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpFwd_char`
    if (true) {
        const sorts = new Array<test_SortDatachar>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpFwd_char)
        sorts.push(new test_SortDatachar("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpFwd_char are not equal: " + sort0.name + ' ' + sortS.name + ' for char')
                }
            }
        }
    }
    // block for comparator `est_sortAllOnCmpInv_char`
    if (true) {
        const sorts = new Array<test_SortDatachar>()
        const bubbled = test_sortCopy(arr)
        bubbleSort(bubbled, 0, bubbled.length, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("bubble", bubbled))

        const insertion = test_sortCopy(arr)
        insertionSort(insertion, 0, insertion.length, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("insertion", insertion))

        const heaped = test_sortCopy(arr)
        heapSort(heaped, 0, heaped.length, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("heap", heaped))

        const quicked = test_sortCopy(arr)
        quickSortImpl3(quicked, 0, quicked.length, quicked.length, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("quick", quicked))

        const quickedInsertion = test_sortCopy(arr)
        quickSortImpl40(quickedInsertion, 0, quickedInsertion.length, quickedInsertion.length, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("quick with insertion", quickedInsertion))

        const just = test_sortCopy(arr)
        sort_subarray(just, test_sortAllOnCmpInv_char)
        sorts.push(new test_SortDatachar("sort()", just))

        let sort0 = sorts.at(0)!
        for (let s = 1; s < sorts.length; s++) {
            let sortS = sorts.at(s)!
            for (let i = 0; i < arr.length; i++) {
                if (sort0.arr[i] != sortS.arr[i]) {
                    console.println(sort0.name + ': ')
                    test_printArr(sort0.arr, 0, arr.length)
                    console.println(sortS.name + ': ')
                    test_printArr(sortS.arr, 0, arr.length)
                    throw new Error("sorts est_sortAllOnCmpInv_char are not equal: " + sort0.name + ' ' + sortS.name + ' for char')
                }
            }
        }
    }
}
// ======== end of tests section ========

function bubbleSort(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    let was = true
    while (was) {
        was = false
        for (let i = startIndex; i < endIndex - 1; i++) {
            if (mustPrecede(arr[i + 1], arr[i])) {
                const tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp
                was = true
            }
        }
    }
}

function insertionSort(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean, initIndex: int = startIndex): void {
    if (startIndex != initIndex) {
        // arr[startIndex - 1] exists and is less than or equal to all elements in range
        for (let i = startIndex + 1; i < endIndex; i++) {
            const tmp = arr[i]
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
        return
    }
    for (let i = startIndex + 1; i < endIndex; i++) {
        const tmp = arr[i]
        if (mustPrecede(tmp, arr[startIndex])) {
            for (let j = i; j > startIndex; j--) {
                arr[j] = arr[j - 1]
            }
            arr[startIndex] = tmp
        } else {
            let pos = i
            while (mustPrecede(tmp, arr[pos - 1])) {
                arr[pos] = arr[pos - 1]
                pos--
            }
            arr[pos] = tmp
        }
    }
}
function heapSortUp(arr: NullishType[], idxFromStart: int, startIndex: int, heapRoot: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    const tmp = arr[startIndex + idxFromStart]
    while (startIndex + idxFromStart > heapRoot) {
        const p = (idxFromStart - 1) / 2
        if (!mustPrecede(arr[startIndex + p], tmp)) {
            break
        }
        arr[startIndex + idxFromStart] = arr[startIndex + p]
        idxFromStart = p
    }
    arr[startIndex + idxFromStart] = tmp
}

// Build max heap with root in startIndex given its children are roots of valid heaps
function heapSortDown(arr: NullishType[], idxFromStart: int, startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    let heapRoot = startIndex + idxFromStart
    let arrIndex = heapRoot
    let childIndex = startIndex + idxFromStart * 2 + 1
    const tmp = arr[arrIndex]
    // Walk heap to bottom and pull max child up on each level
    while (childIndex + 1 < endIndex) {
        if (mustPrecede(arr[childIndex], arr[childIndex + 1])) {
            childIndex++
        }
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
        childIndex = childIndex * 2 - startIndex + 1
    }
    if (childIndex < endIndex) {
        arr[arrIndex] = arr[childIndex]
        arrIndex = childIndex
    }
    arr[arrIndex] = tmp
    // Now heap is valid in all positions but arrIndex
    heapSortUp(arr, arrIndex - startIndex, startIndex, heapRoot, mustPrecede)
}

export function heapSort(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    let len = endIndex - startIndex
    for (let i = len / 2 - 1; i >= 0; i--) {
        heapSortDown(arr, i, startIndex, endIndex, mustPrecede)
    }

    for (let i = endIndex - 1; i > startIndex; i--) {
        // move max element to the end of range
        const tmp = arr[i]
        arr[i] = arr[startIndex]
        arr[startIndex] = tmp
        heapSortDown(arr, 0, startIndex, i, mustPrecede)
    }
}

// Put median of three array elements to arr[index1]
function median3(arr: NullishType[], index1: int, index2: int, index3: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    let swap_idx = index2
    if (mustPrecede(arr[index1], arr[index2])) {
        if (mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index3], arr[index2])) {
            swap_idx = index3
        }
    } else {
        if (!mustPrecede(arr[index3], arr[index1])) {
            return
        }
        if (mustPrecede(arr[index2], arr[index3])) {
            swap_idx = index3
        }
    }
    let tmp = arr[index1]
    arr[index1] = arr[swap_idx]
    arr[swap_idx] = tmp
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the right
function quickSortSplit(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(arr[i], pivot)) {
        i++
    }
    if (i == startIndex + 1) {
        while (i < j && !mustPrecede(arr[j], pivot)) {
            j--
        }
    } else {
        while (!mustPrecede(arr[j], pivot)) {
            j--
        }
    }
    while (i < j) {
        // Here !mustPrecede(arr[i], pivot) and mustPrecede(arr[j], pivot) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (mustPrecede(arr[++i], pivot)) {}
        while (!mustPrecede(arr[--j], pivot)) {}
    }
    let pivotIndex = i - 1
    arr[startIndex] = arr[pivotIndex]
    arr[pivotIndex] = pivot

    return pivotIndex
}

// Split range [startIndex, endIndex) by pivot arr[startIndex] and return pivot position
// Elements equal to pivot go to the left
function quickSortSplitLeft(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): int {
    const pivot = arr[startIndex]
    let i = startIndex + 1
    let j = endIndex - 1
    // No bounds check because pivot is median of three elements
    while (mustPrecede(pivot, arr[j])) {
        j--
    }
    if (j + 1 == endIndex) {
        while (i < j && !mustPrecede(pivot, arr[i])) {
            i++
        }
    } else {
        while (!mustPrecede(pivot, arr[i])) {
            i++
        }
    }
    while (i < j) {
        // Here mustPrecede(pivot, arr[i]) and !mustPrecede(pivot, arr[j]) holds
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        while (!mustPrecede(pivot, arr[++i])) {}
        while (mustPrecede(pivot, arr[--j])) {}
    }
    arr[startIndex] = arr[j]
    arr[j] = pivot

    return j
}

function quickSortImpl3(arr: NullishType[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    while (endIndex - startIndex > 3) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl3(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl3(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}
function quickSortImpl40(arr: NullishType[], startIndex: int, endIndex: int, maxDepth: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    while (endIndex - startIndex > 40) {
        if (--maxDepth == 0) {
            heapSort(arr, startIndex, endIndex, mustPrecede)
            return
        }

        median3(arr, startIndex, endIndex - 1, (startIndex + endIndex) / 2, mustPrecede)
        let p = quickSortSplit(arr, startIndex, endIndex, mustPrecede)
        // make a call for the smaller part of array and continue processing the larger part in the loop
        if (p - startIndex < endIndex - p) {
            quickSortImpl40(arr, startIndex, p, maxDepth, mustPrecede)
            startIndex = p + 1
        } else {
            quickSortImpl40(arr, p + 1, endIndex, maxDepth, mustPrecede)
            endIndex = p
        }
    }
    insertionSort(arr, startIndex, endIndex, mustPrecede)
}

function quickSort(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    let size = endIndex - startIndex
    if (size <= 1) {
        return
    }
    // find log of length to fall back into determenistic O(n logn) sort
    let bits = 32
    for (let i = 2; i < 31; i++) {
        if ((size >> i) == 0) {
            bits = i
            break
        }
    }
    quickSortImpl40(arr, startIndex, endIndex, bits * 3, mustPrecede)
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 *
 * @param startIndex an index to start sorting with, inclusive
 *
 * @param endIndex an index to end sorting, exclusive
 *
 * @example: sort array arr
 * ```
 * sort(arr, 0, arr.length)
 * ```
 */
export function sort_subarray(arr: NullishType[], startIndex: int, endIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new ArrayIndexOutOfBoundsError("sort: bounds verification failed")
    }

    quickSort(arr, startIndex, endIndex, mustPrecede);
}

/**
 * sorts arr in-place
 *
 * @param arr an array to sort
 */
export function sort_subarray(arr: NullishType[], mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    sort_subarray(arr, 0, arr.length, mustPrecede);
}

export function sort_subarray(arr: NullishType[], startIndex: int, mustPrecede: (lhs: NullishType, rhs: NullishType) => boolean): void {
    sort_subarray(arr, startIndex, arr.length, mustPrecede)
}