How to insert value in sorted array and keep array sorted?

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?

Identifying the position to insert would be less computationally complex, and trivial — CertainPerformance, Mar 16 '20 at 08:15
Detecting the index and putting a value there is `O(n)`, while sorting is usually `O(n*log(n))`. Therefore insert at index is better. — VLAZ, Mar 16 '20 at 08:15
It really depends on the size of you array. If it's relativement small, it really won't make a difference. If not, do as others have suggested. Code simplicity/readability is often more important than pure performance. — Nicolas SEPTIER, Mar 16 '20 at 08:16

Alvin Sartor · Answer 1 · 2021-07-27T08:13:24.647

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);

Smart detection should be lower than `O(n)` - it's `O(log(n))` for a sorted array, using binary chop to find the correct index. — VLAZ, Mar 16 '20 at 08:29
@VLAZ you're right! Thanks for pointing that out, I completely forgot about it. I added it to the answer and will add some code for it (the question is closed but maybe it'll still help some lost soul). — Alvin Sartor, Mar 16 '20 at 09:37
Lost soul here, this code results in a `RangeError: Maximum call stack size exceeded.` if the array starts with fewer than 2 elements. This may not be elegant but it fixes the issue: ```function binaryInsertion(arr, element) { if (arr.length==0) return arr.push(element); if (arr.length==1) return element < arr[0] ? arr.unshift(element) : arr.push(element); return binaryHelper(arr, element, 0, arr.length - 1); }``` (Sorry, no code blocks in comments.) — Shaun Inman, Jul 01 '21 at 13:09

How to insert value in sorted array and keep array sorted?

1 Answers1