4

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?

Improve this question
3
  • 2
    Identifying the position to insert would be less computationally complex, and trivial Commented Mar 16, 2020 at 8:15
  • 1
    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. Commented Mar 16, 2020 at 8: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. Commented Mar 16, 2020 at 8:16

1 Answer 1

Reset to default
5

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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