insert-sorted-arr.ts

// tslint:disable no-let

/** Return:
 *
 * - `< 0` if `a` comes before `b`.
 * - `0` if `a` and `b` are equal.
 * - `> 0` if `a` comes after `b`.
 */
type Comparator<T> = (a: T, b: T) => number;

/**
 * Insert an element `t` into a **sorted** array `arr`. Does not mutate
 * the array (returns a copy).
 *
 * This function is using Linear Search to insert the element. It'll
 * give us O(n) as best case.
 *
 * Consider going with Binary Search if you've got huge arrays – that'll
 * make it O(log n) as best case instead.
 */
export const insertInSortedArrLinear = <T>(
    arr: T[],
    t: T,
    comp: Comparator<T>
): T[] => {
    const copy = [...arr];
    copy.splice(linearSearch(copy, t, comp), 0, t);
    return copy;
};

const linearSearch = <T>(arr: T[], t: T, comp: Comparator<T>): number => {
    // Early if pos 0 is already bigger
    if (comp(arr[0], t) > 0) {
        return 0;
    }

    if (comp(arr[arr.length - 1], t) <= 0) {
        return arr.length;
    }

    let i = 1;

    while (
        i < arr.length &&
        !(comp(arr[i], t) > 0 && comp(arr[i - 1], t) <= 0)
    ) {
        i = i + 1;
    }

    return i;
};