Efficient way to insert a number into a sorted array of numbers?

Efficiently Inserting Numbers into Sorted JavaScript Arrays

Discover optimal algorithms and JavaScript techniques for maintaining sorted arrays when inserting new elements, balancing performance and code readability.

Inserting a new number into an already sorted array while maintaining its sorted order is a common task in programming. While simple approaches like push() followed by sort() work, they can be inefficient for large arrays. This article explores various efficient methods in JavaScript, focusing on performance and practical implementation.

Understanding the Challenge: Why Simple Sort is Inefficient

When you have a sorted array and need to add a new element, the most straightforward (but often least efficient) method is to append the new element to the end and then re-sort the entire array. This approach, while easy to implement, has a time complexity of O(N log N) due to the sorting operation, where N is the number of elements in the array. For frequently updated or very large arrays, this can lead to significant performance bottlenecks.

let sortedArray = [1, 5, 10, 15];
sortedArray.push(7);
sortedArray.sort((a, b) => a - b);
console.log(sortedArray); // Output: [1, 5, 7, 10, 15]

Simple but inefficient insertion using push() and sort()

Method 1: Finding the Insertion Point with Binary Search

A more efficient approach involves first finding the correct insertion point for the new element and then using splice() to insert it. The key to efficiency here is using a binary search algorithm to locate the insertion point, which reduces the search time complexity from O(N) (linear scan) to O(log N). Once the index is found, splice() inserts the element, which has a time complexity of O(N) in the worst case (if the element is inserted at the beginning, requiring all subsequent elements to shift).

function findInsertionPoint(arr, val) {
  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    if (arr[mid] === val) {
      return mid; // Value already exists, insert here or after
    } else if (arr[mid] < val) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return low;
}

function insertSorted(arr, val) {
  const index = findInsertionPoint(arr, val);
  arr.splice(index, 0, val);
  return arr;
}

let sortedArray = [1, 5, 10, 15];
console.log(insertSorted(sortedArray, 7)); // Output: [1, 5, 7, 10, 15]
console.log(insertSorted(sortedArray, 0)); // Output: [0, 1, 5, 7, 10, 15]
console.log(insertSorted(sortedArray, 20)); // Output: [0, 1, 5, 7, 10, 15, 20]

Insertion using binary search to find the correct index

Binary Search Flow for Insertion Point

Method 2: Maintaining Sorted Order with a Custom Insertion Function

For scenarios where you frequently insert elements and want to avoid the overhead of splice() for every operation, or if you're building a data structure that inherently maintains sorted order, you might consider a custom insertion function that shifts elements manually. This can sometimes be optimized for specific use cases, though splice() is often highly optimized by JavaScript engines.

function insertSortedManualShift(arr, val) {
  let i = arr.length - 1;
  while (i >= 0 && arr[i] > val) {
    arr[i + 1] = arr[i];
    i--;
  }
  arr[i + 1] = val;
  return arr;
}

let sortedArray = [1, 5, 10, 15];
console.log(insertSortedManualShift(sortedArray, 7)); // Output: [1, 5, 7, 10, 15]
console.log(insertSortedManualShift(sortedArray, 0)); // Output: [0, 1, 5, 7, 10, 15]
console.log(insertSortedManualShift(sortedArray, 20)); // Output: [0, 1, 5, 7, 10, 15, 20]

Custom insertion function with manual element shifting

Choosing the Right Approach

The best method depends on your specific use case:

• Infrequent insertions or small arrays: push() and sort() might be acceptable for its simplicity, but it's generally not recommended for performance-critical applications.
• Frequent insertions into large arrays: Using binary search to find the insertion point followed by splice() is a good balance of readability and performance. Its O(N) complexity is often the best you can achieve with a standard JavaScript array for insertion.
• Extremely performance-critical scenarios or very large datasets: Consider alternative data structures like balanced binary search trees (e.g., AVL trees, Red-Black trees) or skip lists, which offer O(log N) insertion time. However, implementing these from scratch in JavaScript can be complex, and they are not native array types.

Comparison of Insertion Methods