You have to remember the difference between constant speed costs
and computational complexity
. Extra function calls only add extra constant time per element, while sorting an array over-and-over adds extra computational complexity which can't be optimized away (disclaimer: if an array actually is an array in AS3).
Insert into an array has time complexity O(n). Where n is the length of the array. The time it takes to insert a new element into a sorted array with n elements can be written as:arrayInsertTime
(n) = Constant_A * n + Constant_BWhere Constant_A > 0
Insert into a heap has time complexity O(log n), where n is the number of elements in the heap:heapInsertTime
(n) = Constant_C * log(n) + Constant_DWhere Constant_C > 0
Given a large enough value for n, the heap will be faster because n grows much faster than log(n). It doesn't matter how small Constants A and B are, or how big Constants C and D are. As long as you add enough elements, the heap will eventually be faster.Some concrete math using arbitrary numbers:
We'll pretend that the built-in solution has the time formula:arrayInsertTime
(n) = 1*n+1 milliseconds.
So to insert a new element into an array that is 10 long, it would on average take:arrayInsertTime
(10) = 1*10 + 1 = 11 ms
And we assume that the heap has horrible constants, because every function call (etc.) adds a lot of extra cost:heapInsertTime
(n) = 100*log(n)+100 ms
So to insert a new element into a heap with 10 elements would on average take:heapInsertTime
(10) = 100*log(10)+100 ~= 330 ms
But if we try some bigger numbers:
|n||array sort insert (in milliseconds) ||heap insert (in milliseconds)|
|1,000,000 ||1,000,001 ||1,482 |
So even if we try to completely cripple the heap by giving it horrible constants, it wins out pretty quickly. Already at a 1,000 elements it is faster to do the insert into the heap.
Actually calculating the constants isn't really interesting in a real-world situation. You have to do tests to find out when/if the heap catches up. But this shows that the heap is likely (but not guaranteed) to catch up with the built-in sort before you run out of RAM.
Unless, as I mentioned before, an array actually isn't an array but rather a list in AS3. And if AS3 has a engine-powered sort that can make use of an already-sorted list, then that will probably outperform both these options.
Either way: run some tests! (a small disclaimer: my math isn't really rigorous here regarding O(log n) as I ignore the base and stuff, but it does the job of showing the principle.
Also, I have probably missed something obvious, so please correct me where I'm wrong!)