Using quick sort for arrays....

Using quick sort for arrays.

Using quick sort in ArraySort instead of heap sort for better performance.

Committed: http://code.google.com/p/v8/source/detail?r=374

[Mads Ager (chromium), 2008-09-24 12:34:43]

LGTM, except for the following comments.

http://codereview.chromium.org/4065/diff/1/2
File src/array.js (left):

http://codereview.chromium.org/4065/diff/1/2#oldcode724
Line 724: if (IS_ARRAY(this)) {
This piece of code should still be needed.  If we remove array holes, we have to
restore the length afterwards.

http://codereview.chromium.org/4065/diff/1/2
File src/array.js (right):

http://codereview.chromium.org/4065/diff/1/2#newcode674
Line 674: var pivot_index = global.Math.floor(global.Math.random() * (to -
from)) + from;
We need to make sure that we use the original Math.floor and Math.random so that
user-defined versions of Math.random do not interfere with this code.  See for
instance date-delay.js that introduces and uses $floor and $abs for the original
versions of Math.floor and Math.abs.

[mdakin, 2008-09-25 14:25:28]

http://codereview.chromium.org/4065/diff/1/2
File src/array.js (right):

http://codereview.chromium.org/4065/diff/1/2#newcode651
Line 651: // Standard in-place HeapSort algorithm.
I think it is Quicksort now.

http://codereview.chromium.org/4065/diff/1/2#newcode697
Line 697: var length = ToUint32(this.length);
Maybe using insertion sort for small arrays (<10 elements ) would be good. It is
faster than Quicksort for small arrays.