Здравствуйте, _DAle_, Вы писали:

_DA>Может я чего-то не понял, но сложность этой сортировки в худшем случае O(n^2). Например, если взять возрастающую последовательность, то это поисковое дерево вытянется в список. А обгон quick sort получается, видимо, только из-за хранения количества одинаковых чисел и большого количества одинаковых чисел в тестах.

это спецефическая сортировка, вы выбрали самый неудобный для нее вариант
если честно я не стал разбираться с временной сложностей, а просто смотрел на факты...
при большом количестве вариантов (т.е. когда одинаковых значений мало, худшим для TreeSort) у него время всего лишь в 2 раза хуже чем у QuickSort

вот например у меня ListView надо просортировать по столбцу, а у меня там много одинаковых значений... тут TreeSort окажется эффективнее QuickSort потому, что много одинаковых значений и сортировка черпаками потому что сортировать надо не числа а текст (короче вариантов значений валом)
еще раз повторяю — специфическая сортировка