195

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.
林果皞
  • 7,539
  • 3
  • 55
  • 70
Elliot Kroo
  • 4,463
  • 3
  • 23
  • 15
  • using splice in the second implementation is a bit wasteful. Why not use push? – Breton Aug 28 '09 at 01:30
  • Good point, I just copied it from the first. – Elliot Kroo Aug 28 '09 at 04:14
  • 5
    Anything containing `splice()` (e.g. your 1st example) is already O(n). Even if it doesn't internally create a new copy of the entire array, it potentially has to shunt all n items back 1 position if the element is to be inserted in position 0. Maybe it's fast because it's a native function and the constant is low, but it's O(n) nonetheless. – j_random_hacker Jan 02 '11 at 08:19
  • what does start||0 suppose to do? – Charlie Parker Apr 06 '14 at 00:30
  • 6
    also, for future reference for people using this code, the code has a bug when trying to insert to the beginning of the array. Look further down for the corrected code. – Charlie Parker Apr 06 '14 at 00:36
  • 3
    Don't use `parseInt` use `Math.floor` instead. `Math.floor` is much faster than `parseInt`: https://jsperf.com/test-parseint-and-math-floor – Hubert Schölnast Sep 01 '17 at 10:08
  • @j_random_hacker , array.push() would also reserve a space, copy, and place the pushed value. Not much of a difference to splice() then? – Khamaseen Jun 29 '21 at 12:14
  • @Khamaseen: `array.push()` always adds the new element at the end, so it doesn't need to reposition any existing elements. If the internal allocation size increases geometrically (e.g., doubling each time we run out of space), then insertions will be amortised O(1) time. – j_random_hacker Jun 29 '21 at 12:56
  • @j_random_hacker , interesting I thought it would needed to copy. However it are more like ArrayList then? In that case a splice would also not bother that much? – Khamaseen Jun 29 '21 at 14:44
  • @Khamaseen: I don't know what ArrayList you're referring to, or how it's implemented. `array.splice()` necessarily has to move ( = copy) all elements to the right of the inserted element, and this necessarily takes time linear in the number of those elements. `array.push()` does not, because it needs to move ( = copy) zero such elements. `array.push()` *might* be implemented to always reallocate and copy, in which case it would indeed take linear time (in the length of the entire array) each time, but that would be a bad choice of implementation. – j_random_hacker Jun 30 '21 at 00:06
  • @j_random_hacker, I apparently didn't know much about arrays in Javascript. Bottomline to this questioning about splice() is, yes most likely O(n). And push(), depending, most likely there is no copying indeed. Javascripts arrays are implemented differently, though often it seems to be Hashmap kind of structure, or even sometimes a binary tree kind of structure. Okay, didn't know. Cool. – Khamaseen Jun 30 '21 at 07:05
  • If Array is implemented as some balanced tree (AVL, RB, B, ...) then most of these operations are O(log(n)). Specifically, B-trees block sizes can be optimized for the CPU cache line size. – Miguel Angelo Oct 27 '21 at 16:27
  • If Array further optimizes given the functions you use on it, then it could be O(1) most often, e.g. if you use push/shift, then it uses a queue internally, if push/pop then it uses a stack, this all works by pre-allocating memory. If you use a lot of splicing, then a b-tree is perfect, if you only use indexing, then a vector is used. More optimizations are possible with "views", which works great with static content, like strings, data-arrays, in which you never really operate on the original object, but create views into that object. – Miguel Angelo Oct 27 '21 at 16:27
  • The language engine can also help by tracking where these arrays are created, and using the optimal implementation right from the creation moment. JavaScript engines these days have 3+ levels of optimization, it could be done! In the 1st level, where things are still interpreted, it could detect these patterns. And when level 3 optimization arrives, it could hard-code the specific structure there. – Miguel Angelo Oct 27 '21 at 16:31
  • @Khamaseen as you said, a hashmap is also a good idea, for sparse arrays, or arrays which have attributes added. If the same set of attributes are always added, it could be turned into a C-like struct in the implementation level, at one of these optimization levels. – Miguel Angelo Oct 27 '21 at 16:38

18 Answers18

90

Simple (Demo):

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}
Web_Designer
  • 72,308
  • 93
  • 206
  • 262
  • 7
    Nice touch. I never heard of using bitwise operators to find the mid value of two numbers. Normally I would just multiply by 0.5. Is there a significant performance boost doing it this way? – Jackson Jan 24 '16 at 22:45
  • 7
    @Jackson `x >>> 1` is binary right shift by 1 position, which is effectively just a division by 2. e.g. for 11: `1011` -> `101` results to 5. – Qwerty Jan 31 '16 at 17:16
  • 4
    @Qwerty @Web_Designer Being already on this track, could you explain the difference between `>>> 1` and ([seen](https://en.wikipedia.org/wiki/Binary_search_algorithm#Deferred_detection_of_equality) [here](https://github.com/Olical/binary-search/blob/c4911653211990e4b858225d9df4bac511820445/src/binarySearch.js) [and](http://stackoverflow.com/a/20261974/1250044) [there](http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html)) `>> 1`? – yckart Feb 26 '16 at 14:02
  • 6
    `>>>` is an unsigned right shift, whereas `>>` is sign-extending - it all boils down to in-memory representation of negative numbers, where the high bit is set if negative. So if you shift `0b1000` right 1 place with `>>` you'll get `0b1100`, if you instead use `>>>` you'll get `0b0100`. While in the case given in the answer it doesn't really matter (the number being shifted with neither be larger than a signed 32-bit positive integer's max value nor negative), it's important to use the right one in those two cases (you need to pick which case you need to handle). – asherkin Feb 26 '16 at 23:43
  • 3
    @asherkin - This is not right: "if you shift `0b1000` right 1 place with `>>` you'll get `0b1100`". No, you get `0b0100`. The result of the different right shift operators will be the same for all values except negative numbers and numbers greater than 2^31 (ie, numbers with a 1 in the first bit). – gilly3 Aug 02 '16 at 22:32
  • 2
    @gilly3 That example was using 4-bit numbers for the sake of brevity, not 32-bit ones - the explanation where it matters with 32-bit numbers (the same one you just gave me) is in my comment if you read to the end rather than jumping to respond. – asherkin Aug 02 '16 at 22:36
  • 1
    Ok, I see how that helps to illustrate. I think it's important to clarify that your example is illustrative only, and that in practice all numbers are 32 bits when doing binary operations in JavaScript. The JavaScript bitwise operators first convert all input values to 32-bit integers. – gilly3 Aug 02 '16 at 23:38
  • Is the difference between those operators in Java, the same as the difference between those operators in Javascript? I think so. http://stackoverflow.com/questions/2811319/difference-between-and Also, @yckart links off SO, but there's an example of `>>` [right here in this thread](http://stackoverflow.com/a/20261974/1175496), which it expects is **faster** than `>>>` – Nate Anderson Apr 16 '17 at 01:33
  • This is good but probably it could have been better if you had defined `mid` in the function context rather than inside the `while` loop. It gets defined many times over and over and this might form a culprit for the performance in large arrays. – Redu Jan 26 '21 at 18:13
  • Very nice. Well done, sir! :) – Flavio Nov 06 '21 at 19:04
  • 1
    If you use `/ 2` to get mid, don't forget to floor it: `Math.floor((low + high) / 2);` – AnorZaken May 25 '22 at 13:40
  • "`>>>` is an unsigned right shift, whereas `>>` is sign-extending" Wouldn't `>>` be better then, to manage also negative numbers? – Naeio Aug 31 '22 at 13:16
  • instead of `var mid = (low + high) >>> 1;` I preferred: `var sum = low + high; var mid = sum % 2 == 0 ? sum / 2 : (sum - 1) / 2;` This seemed more readable and has comparable performance – Abhishek Borar Apr 12 '23 at 11:06
69

Just as a single data point, for kicks I tested this out inserting 1000 random elements into an array of 100,000 pre-sorted numbers using the two methods using Chrome on Windows 7:

First Method:
~54 milliseconds
Second Method:
~57 seconds

So, at least on this setup, the native method doesn't make up for it. This is true even for small data sets, inserting 100 elements into an array of 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds
Sicco
  • 6,167
  • 5
  • 45
  • 61
Sam Phillips
  • 836
  • 7
  • 5
  • 2
    arrays.sort sounds quite terrible – njzk2 Oct 11 '12 at 07:41
  • 2
    Seems that the array.splice must be doing something really clever, to insert a single element within 54 microseconds. – gnasher729 Jul 21 '15 at 11:03
  • @gnasher729 - I don't think Javascript arrays are really the same as physically continuous arrays like we have in C. I think the JS engines can implement them as a hash map/dictionary enabling the quick insert. – Ian Sep 26 '17 at 17:47
  • 1
    when you use a comparator function with `Array.prototype.sort`, you lose the benefits of C++ because the JS function is called so much. – aleclarson Jun 14 '18 at 14:57
  • How does the First Method compare now that [Chrome uses TimSort](https://stackoverflow.com/a/37245185/2036135)? From [TimSort Wikipedia](https://en.wikipedia.org/wiki/Timsort): "In the best case, which occurs when the input is already sorted, [TimSort] runs in linear time". – poshest Feb 05 '20 at 11:40
  • I struggle to see an answer here. What is meant by "the two methods"? The answer reads like a comment on another answer, I must be missing something very obvious since it has received dozens of votes. – Armen Michaeli Apr 18 '22 at 20:12
  • @amn There are 2 examples in the post, so they must've tested those. – l3l_aze May 29 '22 at 09:53
32

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;
};
Nate Anderson
  • 18,334
  • 18
  • 100
  • 135
kwrl
  • 653
  • 8
  • 12
  • 7
    It seems worth noting, for the record, that this version DOES work correctly when trying to insert to the beginning of the array. (It's worth mentioning it because the version in the original question has a bug and doesn't work correctly for that case.) – garyrob May 01 '14 at 14:58
  • 3
    I'm not sure if my implementation was different, but I needed to change the ternary to `return c == -1 ? pivot : pivot + 1;` in order to return the correct index. Otherwise for an array with length 1 the function would return -1 or 0. – Niel Jul 13 '15 at 18:08
  • It depends on the logic you want. Mine was "return the index of the element which is lower or equal to the element". – kwrl Jul 23 '15 at 16:09
  • Your code will not work for fractions, negative numbers or large integers because the >> bitwise operators casts to unsigned 32 bit. You should use '/ 2' instead of '>>> 1', I'd be surprised if it were slower. – James Apr 04 '16 at 18:22
  • 3
    @James: The parameters start and end are only used on recursive call and will not be used on inital call. Because these are index values for the array they must be of type integer and on recursive call this is implicitly given. – kwrl Apr 05 '16 at 10:12
  • @kwehrle Yes, you are right, my mistake, >> is good in this case. – James Apr 05 '16 at 11:05
  • kwl says "var pivot = (start + end) >> 1; // should be faster than the above calculation" -- does he mean that `>>` should be faster than `>>>` ? – Nate Anderson Apr 16 '17 at 01:39
  • 1
    @TheRedPea: no, I meant `>> 1` should be faster (or not slower) than `/ 2` – kwrl Apr 17 '17 at 15:45
  • Thanks. I guess I've read elsewhere people suggest ("just use `/ 2`, it results in a shift equivalent in the bytecode anyway = same performance; write your code for humans, not for computers' optimizations"). I guess this is why you said "(or not slower)". Agree? Thanks. – Nate Anderson Apr 17 '17 at 17:59
  • @TheRedPea unless humans start compiling and executing code, you're never really writing code for humans. – Pasha Skender Aug 25 '17 at 18:14
  • 1
    I can see a potential issue with the result of `comparer` function. In this algorithm it is compared to `+-1` but it could be arbitrary value `<0` / `>0`. See [compare function](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort). The problematic part is not only the `switch` statement but also the line: `if (end - start <= 1) return c == -1 ? pivot - 1 : pivot;` where `c` is compared to `-1` as well. – eXavier Apr 03 '18 at 14:37
  • 1
    @eXavier: Your absolutely right that in some cases - if there are numerical values to compare where I can simply subtract them to get an sort order - this could be a problem. I always assumed a "clean" comparer function returning just values of `[-1, 0, +1]`. For your case the call to compare could be extended to `var c = Math.sign(comparer(element, array[pivot]));`. But this - and also my - version would fail, if someone provides an exotic comparer returning non numerical values. :( So I stay with my assumption, that the comparer should return only the three mentioned values. – kwrl Apr 04 '18 at 18:12
  • @kwrl OK, I understand but I still think you should mention such assumption explicitly in your answer (it's a bit lost here in comments). Real scenario: I used your algorithm in a function and it worked well as I was using it with array of numbers (BTW thanks for sharing). Later on I imported that function when I needed to sort array of objects by one of its numeric property and used the subtraction comparer which accidentally worked for 2 or 3 items. So I realized the sorting issue later in dev cycle. My fault, of course, but my comment was meant to save others some time.. – eXavier Apr 05 '18 at 06:24
22

There's a bug in your code. It should read:

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

Without this fix the code will never be able to insert an element at the beginning of the array.

Web_Designer
  • 72,308
  • 93
  • 206
  • 262
syntheticzero
  • 331
  • 2
  • 3
  • 1
    why are you or-ing a int with 0? i.e. what does start || 0 do? – Charlie Parker Apr 06 '14 at 00:38
  • 3
    @Pinocchio: start || 0 is a short equivalent of: if(!start) start = 0; - However, the "longer" version is more efficent, because it does not assign a variable to itself. – SuperNova Apr 09 '14 at 13:36
18

I know this is an old question that has an answer already, and there are a number of other decent answers. I see some answers that propose that you can solve this problem by looking up the correct insertion index in O(log n) - you can, but you can't insert in that time, because the array needs to be partially copied out to make space.

Bottom line: If you really need O(log n) inserts and deletes into a sorted array, you need a different data structure - not an array. You should use a B-Tree. The performance gains you will get from using a B-Tree for a large data set, will dwarf any of the improvements offered here.

If you must use an array. I offer the following code, based on insertion sort, which works, if and only if the array is already sorted. This is useful for the case when you need to resort after every insert:

function addAndSort(arr, val) {
    arr.push(val);
    for (i = arr.length - 1; i > 0 && arr[i] < arr[i-1]; i--) {
        var tmp = arr[i];
        arr[i] = arr[i-1];
        arr[i-1] = tmp;
    }
    return arr;
}

It should operate in O(n), which I think is the best you can do. Would be nicer if js supported multiple assignment. here's an example to play with:

Update:

this might be faster:

function addAndSort2(arr, val) {
    arr.push(val);
    i = arr.length - 1;
    item = arr[i];
    while (i > 0 && item < arr[i-1]) {
        arr[i] = arr[i-1];
        i -= 1;
    }
    arr[i] = item;
    return arr;
}

Update 2

@terrymorse pointed out in the comments that javascripts Array.splice method is crazy fast, and it's more than just constant improvement in the time complexity. It seems some linked list magic is being used. It means you still do need a different data structure than a plain array - just that javascript arrays might provide that different data structure natively.

Updated JS Bin link

domoarigato
  • 2,802
  • 4
  • 24
  • 41
  • In JavaScript the insertion sort you propose will be slower than the binary search & splice method, because splice has a fast implementation. – trincot May 07 '19 at 17:27
  • unless javascript somehow can break the laws of time complexity, i'm skeptical . Do you have a runnable example of how the binary search and splice method is faster? – domoarigato May 07 '19 at 21:41
  • I take back my second comment ;-) Indeed, there will be an array size beyond which a B-tree solution will outperform the splice solution. – trincot May 08 '19 at 17:51
  • This "array.push, bubble-swap" method is O(n). It is **much** slower than the "binary search, Array#splice" method, which is O(log n) (splice takes almost no time). On a large array, it is over 100 times faster. See [speed benchmark test](https://jsbench.me/y1km1e95pt). – terrymorse Mar 10 '21 at 23:06
  • @terrymorse unfortunately, Array.splice is not O(log n), it is also O(n) which was the main point of my answer. – domoarigato Mar 11 '21 at 08:41
  • The code I offered is indeed slower than an implementation using splice, because there are some optimizations in the native code, however, the difference is a constant difference, ie. O(n/k), not a difference in the fundamental complexity order. – domoarigato Mar 11 '21 at 08:49
  • 1
    @domoarigato Performance test shows dramatically that [insertion with Array.splice is much less than O(N)](https://jsbench.me/y1km1e95pt). Time/N decreases for every increase in `N` between 100 and 100,000. – terrymorse Mar 11 '21 at 20:32
  • 1
    hmm, it seems that javascript might have implemented some linked list type magic under the hood: https://stackoverflow.com/questions/5175925/whats-the-time-complexity-of-array-splice-in-google-chrome. Thats really cool - but it also just means that a javascript array is not "just an array" and so reinforces the fundamental point of my answer, which that you need another data structure. Thanks for pointing this out @terrymorse – domoarigato Mar 12 '21 at 12:50
  • The way this optimization might be related to memory blocks (cf. https://youtu.be/443UNeGrFoM?t=4975 (at time 1:22:55)) I.e. memory is not contiguous so if you want to insert something. Anyway that video is always great to watch if you are confused about datastructure magic – Felix B. Apr 20 '22 at 09:48
10

Your insertion function assumes that the given array is sorted, it searches directly for the location where the new element can be inserted, usually by just looking at a few of the elements in the array.

The general sort function of an array can't take these shortcuts. Obviously it at least has to inspect all elements in the array to see if they are already correctly ordered. This fact alone makes the general sort slower than the insertion function.

A generic sort algorithm is usually on average O(n ⋅ log(n)) and depending on the implementation it might actually be the worst case if the array is already sorted, leading to complexities of O(n2). Directly searching for the insertion position instead has just a complexity of O(log(n)), so it will always be much faster.

sth
  • 222,467
  • 53
  • 283
  • 367
  • It's worth noting that inserting an element into an array has a complexity of O(n), so the end result should be about the same. – NemPlayer Mar 15 '20 at 17:58
9

Here's a version that uses lodash.

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

note: sortedIndex does a binary search.

I. Cantrell
  • 170
  • 1
  • 7
8

For a small number of items, the difference is pretty trivial. However, if you're inserting a lot of items, or working with a very large array, calling .sort() after each insertion will cause a tremendous amount of overhead.

I ended up writing a pretty slick binary search/insert function for this exact purpose, so I thought I'd share it. Since it uses a while loop instead of recursion, there is no overheard for extra function calls, so I think the performance will be even better than either of the originally posted methods. And it emulates the default Array.sort() comparator by default, but accepts a custom comparator function if desired.

function insertSorted(arr, item, comparator) {
    if (comparator == null) {
        // emulate the default Array.sort() comparator
        comparator = function(a, b) {
            if (typeof a !== 'string') a = String(a);
            if (typeof b !== 'string') b = String(b);
            return (a > b ? 1 : (a < b ? -1 : 0));
        };
    }

    // get the index we need to insert the item at
    var min = 0;
    var max = arr.length;
    var index = Math.floor((min + max) / 2);
    while (max > min) {
        if (comparator(item, arr[index]) < 0) {
            max = index;
        } else {
            min = index + 1;
        }
        index = Math.floor((min + max) / 2);
    }

    // insert the item
    arr.splice(index, 0, item);
};

If you're open to using other libraries, lodash provides sortedIndex and sortedLastIndex functions, which could be used in place of the while loop. The two potential downsides are 1) performance isn't as good as my method (thought I'm not sure how much worse it is) and 2) it does not accept a custom comparator function, only a method for getting the value to compare (using the default comparator, I assume).

Sean the Bean
  • 5,222
  • 5
  • 38
  • 40
5

Here are a few thoughts: Firstly, if you're genuinely concerned about the runtime of your code, be sure to know what happens when you call the built-in functions! I don't know up from down in javascript, but a quick google of the splice function returned this, which seems to indicate that you're creating a whole new array each call! I don't know if it actually matters, but it is certainly related to efficiency. I see that Breton, in the comments, has already pointed this out, but it certainly holds for whatever array-manipulating function you choose.

Anyways, onto actually solving the problem.

When I read that you wanted to sort, my first thought is to use insertion sort!. It is handy because it runs in linear time on sorted, or nearly-sorted lists. As your arrays will have only 1 element out of order, that counts as nearly-sorted (except for, well, arrays of size 2 or 3 or whatever, but at that point, c'mon). Now, implementing the sort isn't too too bad, but it is a hassle you may not want to deal with, and again, I don't know a thing about javascript and if it will be easy or hard or whatnot. This removes the need for your lookup function, and you just push (as Breton suggested).

Secondly, your "quicksort-esque" lookup function seems to be a binary search algorithm! It is a very nice algorithm, intuitive and fast, but with one catch: it is notoriously difficult to implement correctly. I won't dare say if yours is correct or not (I hope it is, of course! :)), but be wary if you want to use it.

Anyways, summary: using "push" with insertion sort will work in linear time (assuming the rest of the array is sorted), and avoid any messy binary search algorithm requirements. I don't know if this is the best way (underlying implementation of arrays, maybe a crazy built-in function does it better, who knows), but it seems reasonable to me. :) - Agor.

agorenst
  • 2,425
  • 14
  • 18
  • 1
    +1 because anything containing `splice()` is already O(n). Even if it doesn't internally create a new copy of the entire array, it potentially has to shunt all n items back 1 position if the element is to be inserted in position 0. – j_random_hacker Jan 02 '11 at 08:19
  • I believe insertion sort is also O(n) best case, and O(n^2) worst case (though the OP's use case is probably best case). – domoarigato May 18 '17 at 08:38
  • 2
    Minus one for talking down to the OP. The first paragraph felt like an unnessessary admonishment of for not knowing how splice works under the hood – Matt Zera Nov 13 '19 at 22:35
3

Here's a comparison of four different algorithms for accomplishing this: https://jsperf.com/sorted-array-insert-comparison/1

Algorithms

Naive is always horrible. It seems for small array sizes, the other three dont differ too much, but for larger arrays, the last 2 outperform the simple linear approach.

gabtub
  • 1,460
  • 2
  • 18
  • 21
  • Why not test data structures designed to implement fast insertion and searching? ex. skip lists and BSTs. https://stackoverflow.com/a/59870937/3163618 – qwr Jan 23 '20 at 02:50
  • 1
    How does Native compare now that [Chrome uses TimSort](https://stackoverflow.com/a/37245185/2036135)? From [TimSort Wikipedia](https://en.wikipedia.org/wiki/Timsort): "In the best case, which occurs when the input is already sorted, it runs in linear time". – poshest Feb 05 '20 at 11:36
2

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?

qwr
  • 9,525
  • 5
  • 58
  • 102
  • 1
    How does this answer `Is there a good reason to choose [splice into location found] over [push & sort]?` – greybeard Jan 23 '20 at 03:17
  • 1
    @greybeard It answers the title. cynically neither choice is efficient. – qwr Jan 23 '20 at 03:23
  • Neither option could be efficient if they involve copying many elements of an array over. – qwr Jan 23 '20 at 03:28
1

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

Don't re-sort after every item, its overkill..

If there is only one item to insert, you can find the location to insert using binary search. Then use memcpy or similar to bulk copy the remaining items to make space for the inserted one. The binary search is O(log n), and the copy is O(n), giving O(n + log n) total. Using the methods above, you are doing a re-sort after every insertion, which is O(n log n).

Does it matter? Lets say you are randomly inserting k elements, where k = 1000. The sorted list is 5000 items.

  • Binary search + Move = k*(n + log n) = 1000*(5000 + 12) = 5,000,012 = ~5 million ops
  • Re-sort on each = k*(n log n) = ~60 million ops

If the k items to insert arrive whenever, then you must do search+move. However, if you are given a list of k items to insert into a sorted array - ahead of time - then you can do even better. Sort the k items, separately from the already sorted n array. Then do a scan sort, in which you move down both sorted arrays simultaneously, merging one into the other. - One-step Merge sort = k log k + n = 9965 + 5000 = ~15,000 ops

Update: Regarding your question.
First method = binary search+move = O(n + log n). Second method = re-sort = O(n log n) Exactly explains the timings you're getting.

Himanshu
  • 31,810
  • 31
  • 111
  • 133
  • yes, but no, it depends on your sort algorithm. Using a bubble sort in the reverse order, your sort if the last element is not sorted is always in o(n) – njzk2 Oct 11 '12 at 07:40
0

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"]
phamhongphuc
  • 19
  • 1
  • 6
0

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.

Redu
  • 25,060
  • 6
  • 56
  • 76
0
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)
Sai Ram
  • 4,196
  • 4
  • 26
  • 39
0

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);
noseratio
  • 59,932
  • 34
  • 208
  • 486
-1
function insertOrdered(array, elem) {
    let _array = array;
    let i = 0;
    while ( i < array.length && array[i] < elem ) {i ++};
    _array.splice(i, 0, elem);
    return _array;
}
Marina
  • 1
  • 2