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.
[ Parent
| on HN ]
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.