On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd <[email protected]> wrote:
> I'll state it again since I guess maybe the third time is the charm:
>
> When I said 'always stable' or 'always unstable' i was referring to which
> implementation the browser uses, not what the sort actually does. There's
> nothing beneficial about the fact that an unstable sort happens to
> rearrange elements. My point is that explicitly forbidding Array.sort from
> conditionally switching between sort implementations (or at least from
> switching between implementations with observable differences) is
> beneficial to users. Let's not be ridiculous here.
>
>
Switching to other insertion sort for small input sizes is a key part of
getting high performance out of quicksort. The insertion sort is used as
the base case of the recursion, and I wouldn't really consider it
"switching between sort implementations". There is no check like the
following:
Array.prototype.sort = function (cmp) {
if (this.length < 20) {
doInsertionSort(this);
} else {
doQuicksort(this);
}
};
It's more like:
Array.prototype.sort = function (cmp) {
quicksortRec(this, 0, this.length, cmp);
};
function quicksortRec(arr, begin, end, cmp) {
if (end - begin < 20) {
fastBaseCase(arr, begin, end, cmp); // what this does happens to be
stable
return;
}
// ... slow recursive case
}
-- Sean Silva
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
