<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd <span dir="ltr"><<a href="mailto:kevin.gadd@gmail.com" target="_blank">kevin.gadd@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I'll state it again since I guess maybe the third time is the charm:<br><br>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.<span class="HOEnZb"><font color="#888888"><br>


</font></span></div><div class="gmail_extra"><br></div></blockquote><div><br></div><div style>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:</div>
<div style><br></div><div style>Array.prototype.sort = function (cmp) {</div><div style>  if (this.length < 20) {</div><div style>    doInsertionSort(this);</div><div style>  } else {</div><div style>    doQuicksort(this);</div>
<div style>  }</div><div style>};</div><div style><br></div><div style>It's more like:</div><div style><br></div><div style>Array.prototype.sort = function (cmp) {<br>  quicksortRec(this, 0, this.length, cmp);</div><div style>
};</div><div style><br></div><div style>function quicksortRec(arr, begin, end, cmp) {</div><div style>  if (end - begin < 20) {</div><div style>    fastBaseCase(arr, begin, end, cmp); // what this does happens to be stable</div>
<div style>    return;<br>  }</div><div style>  // ... slow recursive case<br>}</div><div style><br></div><div style>-- Sean Silva</div></div></div></div>