News for hackers. Stuff that matters.
Re:Writing a Non-Blocking JavaScript Quicksort by KayEss on Wednesday June 10, 2015 @01:24AM (#9690234)
The 'long tail' really oughtn't be that long if they switched to the native sort when a partition becomes small enough.
Re:Writing a Non-Blocking JavaScript Quicksort by drostie on Wednesday June 10, 2015 @12:20PM (#9693329)
That's going to be tricky to do with quicksort... you could definitely do it with mergesort, though, but you'd have to abandon the in-place guarantee.

The basic problem is that Array.prototype.sort() does not accept indexes for a slice of the array to sort between.

Re:Writing a Non-Blocking JavaScript Quicksort by KayEss on Wednesday June 10, 2015 @11:06PM (#9697210)
It's simple enough if you split the list at the partition point, but hard if you do it in place.
Re:Writing a Non-Blocking JavaScript Quicksort by girvo on Wednesday June 10, 2015 @02:39AM (#9690409)
> switched to the native sort when a partition becomes small enough

Isn't that exactly what they are doing?

>> Our approach was simply to prefer the native implementation unless working in IE8 or with arrays over a thousand items.

Re:Writing a Non-Blocking JavaScript Quicksort by gpvos on Wednesday June 10, 2015 @05:08AM (#9690756)
I understood that they chose between the two versions at the top level, not at lower levels.