Efficiently insert a number to an already sorted array of numbers. Can easily be extended for other types or objects.

insert.ts

export const getPositionToInsert = (
  numbers: number[],
  numberToInsert: number
) => {
  if (numberToInsert < numbers[0]) return 0;
  if (numberToInsert > numbers[numbers.length - 1]) return numbers.length;

  const getIndex = (start: number, end: number): number => {
    if (numbers[start] === numberToInsert) return start;
    if (numbers[end] === numberToInsert) return end;

    const middle = start + Math.floor((end - start) / 2);
    if (middle === start) return -1;
    const middleNumber = numbers[middle];

    if (middleNumber === numberToInsert) return middle;
    else if (numberToInsert > middleNumber) return getIndex(middle, end);
    else return getIndex(start, middle);
  };
  return getIndex(0, numbers.length);
};

insert_bench.ts

import { getPositionToInsert } from './insert.ts';

const TEST_LENGTH = 100_000;

const numbers1: number[] = [];
const numbers2: number[] = [];

for (let i = 0; i < TEST_LENGTH; i++) {
  numbers1.push(i);
  numbers2.push(i);
}

const randomNumber = Math.floor(Math.random() * TEST_LENGTH);

Deno.bench('Insert then sort', () => {
  numbers1.push(randomNumber);
  numbers1.sort();
});

Deno.bench('Insert in precise position', () => {
  const positionToInsert = getPositionToInsert(numbers2, randomNumber);
  numbers2.splice(positionToInsert, 0, randomNumber);
});

Benchmarks (100,000 items):

❯ deno bench insert_bench.ts
Check file:///home/anurag/Developer/Hobby/bench/insert_bench.ts
cpu: Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz
runtime: deno 1.34.3 (x86_64-unknown-linux-gnu)

file:///home/anurag/Developer/Hobby/bench/insert_bench.ts
benchmark                       time (avg)             (min … max)       p75       p99      p995
------------------------------------------------------------------ -----------------------------
Insert then sort                 2.44 ms/iter     (2.25 ms … 7.51 ms)   2.43 ms   3.15 ms   3.15 ms
Insert in precise position       13.3 µs/iter   (5.11 µs … 683.95 µs)  14.55 µs  17.13 µs  18.79 µs