Решение найдено. Никакой вставки вообще делать не буду, так как простой перебор дает приличную скорость. При этом скорость добавления вообще супер-пупер-быстрая (просто push в конец массива)
Хотя, был удивлен тем, что конструкция вида
for(var i=0;i<arr.length;i++)
работает быстрее
for(var i in arr)
Почему-то всегда считал, что in быстрее цикла работает. Но при тесте в FF получил 50ms против 125ms