Quicksort: Choose pivot with recursive sort of pivot candidates on large arrays to avoid patholgi...

Quicksort: Choose pivot with recursive sort of pivot candidates on large arrays to avoid patholgical cases.
Committed: http://code.google.com/p/v8/source/detail?r=11873

[danno, 2012-06-19 14:52:17]

How about adding a unit test that triggers the slow behavior in the current
implementation?

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js
File src/array.js (right):

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js#newcod...
src/array.js:781: var t_array = [];
How about creating an InternalArray of the appropriate size here? That obviates
the need for the push() stub call later (you can just assign to the element)

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js#newcod...
src/array.js:802: third_index = GetThirdIndex(a, from, to);
It still seems to be the case that you can carefully construct an array that
triggers the worst case. Is that something we need to avoid?

[Erik Corry, 2012-06-19 18:36:29]

Regression test uploaded

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js
File src/array.js (right):

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js#newcod...
src/array.js:781: var t_array = [];
On 2012/06/19 14:52:17, danno wrote:
> How about creating an InternalArray of the appropriate size here? That
obviates
> the need for the push() stub call later (you can just assign to the element)

OK I tried that and it ended badly.  I have to be 100% sure I get the length
right and there are multiple chances to make off by 1 errors.  Leaving as it is
unless you feel very strongly about this.

https://chromiumcodereview.appspot.com/10532193/diff/6001/src/array.js#newcod...
src/array.js:802: third_index = GetThirdIndex(a, from, to);
On 2012/06/19 14:52:17, danno wrote:
> It still seems to be the case that you can carefully construct an array that
> triggers the worst case. Is that something we need to avoid?

I think we don't as long as it can't happen accidentally.  There is no longer a
stack overflow risk.

[danno, 2012-06-19 19:55:55]

lgtm

http://codereview.chromium.org/10532193/diff/6001/src/array.js
File src/array.js (right):

http://codereview.chromium.org/10532193/diff/6001/src/array.js#newcode781
src/array.js:781: var t_array = [];
Nah, it's fine. I'd rather have the readable code and know it's right.

On 2012/06/19 18:36:29, Erik Corry wrote:
> On 2012/06/19 14:52:17, danno wrote:
> > How about creating an InternalArray of the appropriate size here? That
> obviates
> > the need for the push() stub call later (you can just assign to the element)
> 
> OK I tried that and it ended badly.  I have to be 100% sure I get the length
> right and there are multiple chances to make off by 1 errors.  Leaving as it
is
> unless you feel very strongly about this.