UserAgent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:63.0) Gecko/20100101 Firefox/63.0

Steps to reproduce the problem:
1. Create a custom sort function to count comparisons
2. Call [0, 2, 1].sort(countFunc)
3. Notice that 4 comparisons were used, when there are only 3 pairwise combinations of elements.

What is the expected behavior?
Array.sort should not make the same comparison twice. Permutations of length 3 should be sorted in 2 or 3 steps.

What went wrong?
Timsort makes the same comparison multiple times. The attached `index.html` demonstrates the problem for arrays of length 3. This issue can lead to thousands of extra comparisons on large arrays.

I filed a parallel bug with Python[1], which is the model for Chromium's Torque implementation[2].

The `sort-fix.diff` attachment is my proposed fix for Python. It may be worth following the other bug to see if people reject or improve it.

[1] https://bugs.python.org/issue35369
[2] https://v8.dev/blog/array-sort

Did this work before? No 

Chrome version: 70.0.3538.77 (Official Build) Built on Ubuntu , running on Ubuntu 18.04 (64-bit)  Channel: stable
OS Version: Ubuntu 18.04
Flash Version:
 

Deleted: index.html 883 bytes

index.html 883 bytes View Download

Deleted: sort-fix.diff 2.5 KB

sort-fix.diff 2.5 KB Download