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

user_95840 0
Viewed 151100

I have a sorted JavaScript array, and want to insert one more item into the array such the resulting array remains sorted. I could certainly implement a simple quicksort-style insertion function:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[WARNING] this code has a bug when trying to insert to the beginning of the array, e.g. insert(2, [3, 7 ,9]) produces incorrect [ 3, 2, 7, 9 ].

However, I noticed that implementations of the Array.sort function might potentially do this for me, and natively:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

Is there a good reason to choose the first implementation over the second?

Edit: Note that for the general case, an O(log(n)) insertion (as implemented in the first example) will be faster than a generic sorting algorithm; however this is not necessarily the case for JavaScript in particular. Note that:

  • Best case for several insertion algorithms is O(n), which is still significantly different from O(log(n)), but not quite as bad as O(n log(n)) as mentioned below. It would come down to the particular sorting algorithm used (see Javascript Array.sort implementation?)
  • The sort method in JavaScript is a native function, so potentially realizing huge benefits -- O(log(n)) with a huge coefficient can still be much worse than O(n) for reasonably sized data sets.
sorting algorithm javascript
18 Answers

Very good and remarkable question with a very interesting discussion! I also was using the Array.sort() function after pushing a single element in an array with some thousands of objects.

I had to extend your locationOf function for my purpose because of having complex objects and therefore the need for a compare function like in Array.sort():

function locationOf(element, array, comparer, start, end) {
    if (array.length === 0)
        return -1;

    start = start || 0;
    end = end || array.length;
    var pivot = (start + end) >> 1;  // should be faster than dividing by 2

    var c = comparer(element, array[pivot]);
    if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;

    switch (c) {
        case -1: return locationOf(element, array, comparer, start, pivot);
        case 0: return pivot;
        case 1: return locationOf(element, array, comparer, pivot, end);
    };
};

// sample for objects like {lastName: 'Miller', ...}
var patientCompare = function (a, b) {
    if (a.lastName < b.lastName) return -1;
    if (a.lastName > b.lastName) return 1;
    return 0;
};
user_8780710

Here's a version that uses lodash.

const _ = require('lodash');
sortedArr.splice(_.sortedIndex(sortedArr,valueToInsert) ,0,valueToInsert);

note: sortedIndex does a binary search.

user_77287020

The best data structure I can think of is an indexed skip list which maintains the insertion properties of linked lists with a hierarchy structure that enables log time operations. On average, search, insertion, and random access lookups can be done in O(log n) time.

An order statistic tree enables log time indexing with a rank function.

If you do not need random access but you need O(log n) insertion and searching for keys, you can ditch the array structure and use any kind of binary search tree.

None of the answers that use array.splice() are efficient at all since that is on average O(n) time. What's the time complexity of array.splice() in Google Chrome?

user_31636180

Here is my function, uses binary search to find item and then inserts appropriately:

function binaryInsert(val, arr){
    let mid, 
    len=arr.length,
    start=0,
    end=len-1;
    while(start <= end){
        mid = Math.floor((end + start)/2);
        if(val <= arr[mid]){
            if(val >= arr[mid-1]){
                arr.splice(mid,0,val);
                break;
            }
            end = mid-1;
        }else{
            if(val <= arr[mid+1]){
                arr.splice(mid+1,0,val);
                break;
            }
            start = mid+1;
        }
    }
    return arr;
}

console.log(binaryInsert(16, [
    5,   6,  14,  19, 23, 44,
   35,  51,  86,  68, 63, 71,
   87, 117
 ]));

user_118610560

TypeScript version with custom compare method:

const { compare } = new Intl.Collator(undefined, {
  numeric: true,
  sensitivity: "base"
});

const insert = (items: string[], item: string) => {
    let low = 0;
    let high = items.length;

    while (low < high) {
        const mid = (low + high) >> 1;
        compare(items[mid], item) > 0
            ? (high = mid)
            : (low = mid + 1);
    }

    items.splice(low, 0, item);
};

Use:

const items = [];

insert(items, "item 12");
insert(items, "item 1");
insert(items, "item 2");
insert(items, "item 22");

console.log(items);

// ["item 1", "item 2", "item 12", "item 22"]
user_28999380

Had your first code been bug free, my best guess is, it would have been how you do this job in JS. I mean;

  1. Make a binary search to find the index of insertion
  2. Use splice to perform your insertion.

This is almost always 2x faster than a top down or bottom up linear search and insert as mentioned in domoarigato's answer which i liked very much and took it as a basis to my benchmark and finally push and sort.

Of course under many cases you are probably doing this job on some objects in real life and here i have generated a benchmark test for these three cases for an array of size 100000 holding some objects. Feel free to play with it.

user_45432070 
function insertElementToSorted(arr, ele, start=0,end=null) {
    var n , mid
    
    if (end == null) {
        end = arr.length-1;
    }
    n = end - start 
     
    if (n%2 == 0) {
        mid = start + n/2;        
    } else {
      mid = start + (n-1)/2
    }
    if (start == end) {
        return start
    }
 

    if (arr[0] > ele ) return 0;
    if (arr[end] < ele) return end+2; 
    if (arr[mid] >= ele  &&   arr[mid-1] <= ele) {
        return mid
    }

    if (arr[mid] > ele  &&   arr[mid-1] > ele) {
        return insertElementToSorted(arr,ele,start,mid-1)    
    }

    if (arr[mid] <= ele  &&   arr[mid+1] >= ele) {
        return  mid + 1
    }

    if (arr[mid] < ele  &&   arr[mid-1] < ele) {
        return insertElementToSorted(arr,ele,mid,end)
    }

    if(arr[mid] < ele  &&   arr[mid+1] < ele) {
           console.log("mid+1", mid+1, end)
          return insertElementToSorted(arr,ele,mid+1,end)
    
    }
}

// Example

var test = [1,2,5,9, 10, 14, 17,21, 35, 38,54, 78, 89,102];
insertElementToSorted(test,6)
user_42214200

As a memo to my future self, here is yet another version, findOrAddSorted with some optimizations for corner cases and a rudimentary test.

// returns BigInt(index) if the item has been found
// or BigInt(index) + BigInt(MAX_SAFE_INTEGER) if it has been inserted 
function findOrAddSorted(items, newItem) {
  let from = 0;
  let to = items.length;
  let item;

  // check if the array is empty
  if (to === 0) {
    items.push(newItem);
    return BigInt(Number.MAX_SAFE_INTEGER);
  }

  // compare with the first item
  item = items[0];
  if (newItem === item) {
    return 0;
  }
  if (newItem < item) {
    items.splice(0, 0, newItem);
    return BigInt(Number.MAX_SAFE_INTEGER);
  }

  // compare with the last item
  item = items[to-1];
  if (newItem === item) {
    return BigInt(to-1);
  }
  if (newItem > item) {
    items.push(newItem);
    return BigInt(to) + BigInt(Number.MAX_SAFE_INTEGER);
  }

  // binary search
  let where;
  for (;;) {
    where = (from + to) >> 1;
    if (from >= to) {
      break;
    }

    item = items[where];
    if (item === newItem) {
      return BigInt(where);
    }
    if (item < newItem) {
      from = where + 1;
    }
    else {
      to = where;
    }
  }

  // insert newItem
  items.splice(where, 0, newItem);
  return BigInt(where) + BigInt(Number.MAX_SAFE_INTEGER);
}

// generate a random integer < MAX_SAFE_INTEGER
const generateRandomInt = () => Math.floor(Math.random() * Number.MAX_SAFE_INTEGER);

// fill the array with random numbers
const items = new Array();
const amount = 1000;
let i = 0;
let where = 0;
for (i = 0; i < amount; i++) {
  where = findOrAddSorted(items, generateRandomInt());
  if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
    break;
  }
}

if (where < BigInt(Number.MAX_SAFE_INTEGER)) {
  console.log(`items: ${i}, repeated at ${where}: ${items[Number(where)]}`)
}
else {
  const at = Number(where - BigInt(Number.MAX_SAFE_INTEGER));
  console.log(`items: ${i}, last insert at: ${at}: ${items[at]}`);
}
console.log(items);

user_17683030
Related