Для пузырька убывающий массив действительно худший возможный случай, и единственное, что могу предположить,— JIT и предсказание ветвлений на уровне процессора. Ради интереса перейди на устаревшую виртуальную машину — думаю, этот случай сразу же станет худшим.
Для быстрой убывающий массив — один из лучших случаев, будет сделано ровно [n/2] обменов. Легко показать, что элементы в начале и конце массива, стоящие на своих местах, быстрая сортировка не сместит никогда. Так что первое, что сделает сортировка,— разобьёт на меньший (отсортированный) и больший (частично отсортированный как надо, частично — в обратном порядке). Ту часть, которая как надо, сортировка не тронет. А ту, которая наоборот — задействуем трансфинитную индукцию, и получаем, что ровно [n/2].
