V>С тем, что Вы написали, спорить не приходится. Я спрашивал именно о пузырьке и как он может быть быстрее q-сорта.

Стандартный вариант пузырька делает не жёстко заданные n-1 проходов, а выполняет проходы до тех пор, пока делается хотя бы одна перестановка. Если данные уже почти отсортированы, т.е. все элементы находятся от своих правильных мест не далее чем на k позиций, то он потребует порядка k*n операций, а не n*log(n), как квик в лучшем случае (и в среднем), а хип — в худшем. Соответственно, если n~=2^25, а k~=5, то получим выигрыш в 5 раз.