Представьте себе случай, когда сравнение двух элементов чрезвычайно дорого.

Какой алгоритм сортировки вы бы использовали?

Какой алгоритм сортировки использует наименьшее количество сравнений в среднем случае?

Что если вы можете ожидать, что многие сравниваемые элементы будут идентичны, скажем, в 80% сравнений. Есть ли разница?