Add heapsort fallback to Generics.Collections.TArrayHelper.Sort.
First of all, I’d rather see generic Sort() with static, inlineable comparer (like this one) in System (just like Utf8CodepointLen) to be (re)used everywhere (I also did some research about minimizing its code bloat by moving type-dependent parts into callbacks supplied to a non-generic core), but you will likely object.
So this merge request just adds a heapsort fallback to Generics.Collections.TArray.Sort, protecting it against O(n²) time.
On my computer, this demo:
before the MR, outputs
--- strings ---
Order: random.
n = 1500: 3.5 ms/sort, OK
n = 3000: 6.7 ms/sort (1.9x from previous), OK
n = 6000: 14.1 ms/sort (2.1x from previous), OK
Order: QSort killer.
n = 1500: 142.7 ms/sort, OK
n = 3000: 553.0 ms/sort (3.9x from previous), OK
n = 6000: 2186.0 ms/sort (4.0x from previous), OK
--- float32's ---
Order: random.
n = 10000: 1.0 ms/sort, OK
n = 20000: 2.0 ms/sort (2.1x from previous), OK
n = 40000: 4.4 ms/sort (2.1x from previous), OK
Order: QSort killer.
n = 10000: 74.3 ms/sort, OK
n = 20000: 294.0 ms/sort (4.0x from previous), OK
n = 40000: 1169.0 ms/sort (4.0x from previous), OKshowing perfect O(n²) and huge slowdown on bad cases that are very easy to build, even for more complex strategies like median-3.
After the MR (but with Median simplified back to p + (n - 1) div 2, so that the same “QSort killer” still triggered the worst QSort case), output is
--- strings ---
Order: random.
n = 1500: 3.1 ms/sort, OK
n = 3000: 7.4 ms/sort (2.4x from previous), OK
n = 6000: 15.5 ms/sort (2.1x from previous), OK
Order: QSort killer.
n = 1500: 7.8 ms/sort, OK
n = 3000: 17.9 ms/sort (2.3x from previous), OK
n = 6000: 38.2 ms/sort (2.1x from previous), OK
--- float32's ---
Order: random.
n = 10000: 1.0 ms/sort, OK
n = 20000: 2.0 ms/sort (2.1x from previous), OK
n = 40000: 4.4 ms/sort (2.2x from previous), OK
Order: QSort killer.
n = 10000: 1.6 ms/sort, OK
n = 20000: 3.3 ms/sort (2.2x from previous), OK
n = 40000: 7.1 ms/sort (2.1x from previous), OK