Array#sort() implementations not interoperable

Sean Silva silvas at purdue.edu
Thu Jun 13 17:12:15 PDT 2013


On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd <kevin.gadd at gmail.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130613/8e564480/attachment.html>


More information about the es-discuss mailing list