0

The requirement is to start with an empty array, and insert elements into it, one at a time, but keep the array sorted in ascending order. A use of this would be to find the running median of a set of periodic inputs. I have tried simply pushing an element and then invoking the built-in sort method, but appears (by some benchmarks others have done on jsPerf) to slow down with large number of elements.

Duplicates are to be allowed (although a simple trick will let me disallow them as well).

function binaryInsert(x, array) {
    var l = 0,
        r = array.length - 1,
        m;
    while (l <= r) {
        m = (l + r) / 2 | 0;
        if (array[m] > x) {
            r = m - 1;
            continue;
        }
        l = m + 1;
        if (array[m] === x) {
            break; // change to return to avoid duplicates
        }
    }
    array.splice(l, 0, x);
}

I did look at this, but that seems to be doing a recursive search, which does not appear to be optimal without tail call optimization.

Also, are there any alternatives to the splice at the end?

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
Shripathi Kamath
  • 310
  • 3
  • 10
  • This may interest you - http://stackoverflow.com/questions/25109518/how-do-i-convert-this-nested-iteration-to-a-recursive-solution – jdphenix Feb 03 '15 at 07:05

1 Answers1

-1

You should ask yourself a couple questions:

  1. Do I need to keep elements sorted at any time?
  2. How critical is performance for you?

If your answer to question 1 is NO then I'd say go ahead pushing and sorting but don't sort it everytime you push a new element but just one at the very end of elements insertion.

If that answer was YES then pushing and sorting is not for you. If that's the case then we need to answer question 2.

If your answer to question 2 is YES then I'd say you should go with binary recursive algorithm or even better you use a different data structure, one letting you insert quite fast keeping them sorted and more than that retrieving fast enough. That is a binary tree!

Sergio Amador
  • 9