Да, из простых алгоритмов сортировка выбором - наилучшая. Там сравнений n^2, а перестановок только n - что и дает выигрыш. Сравнение-то это только одна команда процессора.
Кстати, в книге Бентли "обсасывается" бинарный поиск. Первая исходная версия и конечная оптимизированная различаются по быстродействию в 8 раз.