How to insert value in sorted array and keep array sorted? [duplicate]

Question

What is the best way to insert value in an array and keep the array sorted?

for example here is an array

const arr = [1, 4, 23, 45];

I can add a new value using method push or splice, for example 16, and I'll get modified array:

[1, 4, 23, 45, 16]

But I need to keep array sorted:

[1, 4, 16, 23, 45]

What is the better way to keep array sorted? Should I sort every time when add a new value, or detect necessary index for inserting a new value?

Answer 1

Just look at the complexities:

• SORTING: O(nlogn) in the best scenario
• INDEX INSERT: O(n) in the worst scenario
• SORTING SMART: O(n) in the best scenario, using algorithms like insertionSort, that work very well when the array is almost already sorted
• BINARY INSERTION: O(logn) this is the preferred way

function  binaryInsertion(arr, element) {
    return binaryHelper(arr, element, 0, arr.length - 1);
}

function binaryHelper(arr, element, lBound, uBound) {
    if (uBound - lBound === 1) {
        // binary search ends, we need to insert the element around here       
        if (element < arr[lBound]) arr.splice(lBound, 0, element);
        else if (element > arr[uBound]) arr.splice(uBound+1, 0, element);
        else arr.splice(uBound, 0, element);
    } else {       
        // we look for the middle point
        const midPoint = Math.floor((uBound - lBound) / 2) + lBound;
        // depending on the value in the middle, we repeat the operation only on one slice of the array, halving it each time
        element < arr[midPoint]
            ? binaryHelper(arr, element, lBound, midPoint)
            : binaryHelper(arr, element, midPoint, uBound);
    }
}

console.log("even array test");
var array = [1,3,4,5,9];
binaryInsertion(array, 2);
console.log(array);

console.log("odd array test");
var array = [1,3,5,7,9,11,13,15];
binaryInsertion(array, 10);
console.log(array);

console.log("beginning and end test");
var array = [2,3,4,5,9];
binaryInsertion(array, 0);
binaryInsertion(array, 10);
console.log(array);