mono/mono — pull request #421 by martinpotter (2012-08-06 05:43:26+00:00)
Title: Bug #6406: Revert to prior quick sort implementation.

Large arrays with lots of duplicate values can result in stack overflow when the left "wall" is moved in when the value is less than or equal to the pivot. Restoring the previous behavior where it was only moved if the value was less than the pivot. This results in more swaps, but similar performance; except in the case where there are lots of duplicate values, which is considerably faster using the previous implementation.

Reverted to the previous implementation of the various qsort methods, added back in the insertion sort optimization for small arrays and updated the algorithm to only recurse on the smaller partition, avoiding the stack overhead when recursing on the larger partition.

Added the insertion sort optimization for small arrays to the non-generic version of qsort.