Re-enable QSort killer O(N²) detection, make it deterministic and instant.

Though I neglect tests and very rarely run my FPC test suite, I did it a number of times so far (5 maybe), and 100% of them were like that:

1. I run cd tests & make full TEST_FPC=ppcx64.exe.

2. I alt-tab to the game / IDE / going for tea / whatever.

3. Time passes.

4. My CPU fan that absolutely didn’t care about the game nor the rest of the suite starts spinning.

5. I alt-tab to the console and see it running my “QSort killer” for the next 30 seconds (that’s how it works: waits for 3 second worth of sorts, in each of 12 scenarios).

Well, first of all, in my defense, it wasn’t supposed to be a test. But as a test, it takes a huge amount of time, and its failures were silenced shortly after it was introduced because it measured time which is inherently very unreliable.

Obvious solution is measuring comparison count with custom comparers. It departs from the original idea (only mathematicians care about comparison count per se, users care about time), but allows the test to run instantly and deterministically.

There is a widely known, or at least easily googleable way, from which the mere name “QSort killer” originates, to have an universal QSort killer making up a bad case through a custom comparer, not dependent (unlike mine) on the median selection strategy. But I deliberately didn’t do that from the start because considered it cheating, unlike explicitly contriving the array. (They say this method can be modified to build the array, too, but this must be complex.)

Output after the MR with heapsort fallback disabled:

--- strings ---

Order: random.
n = 1500:   23619 comparisons, OK
n = 3000:   51650 comparisons (2.2x from previous), OK
n = 6000:   111817 comparisons (2.2x from previous), OK

Order: QSort killer.
n = 1500:   571491 comparisons, OK
n = 3000:   2267991 comparisons (4.0x from previous), potentially bad sorting algorithm behaviour
n = 6000:   9035991 comparisons (4.0x from previous), potentially bad sorting algorithm behaviour

--- float32's ---

Order: random.
n = 10000:  190575 comparisons, OK
n = 20000:  400980 comparisons (2.1x from previous), OK
n = 40000:  882602 comparisons (2.2x from previous), OK

Order: QSort killer.
n = 10000:  25059991 comparisons, OK
n = 20000:  100119991 comparisons (4.0x from previous), potentially bad sorting algorithm behaviour
n = 40000:  400239991 comparisons (4.0x from previous), potentially bad sorting algorithm behaviour

Something was wrong, see above.