Сортировки пузырьком, поскольку именно он и рассматривается в статье.
Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.

Потому-что алгоритм имеет сложность O(n^2)

«Алгоритмы: построение и анализ» Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

На мой взгляд очень хорошая книга

Операций вы должны будете выполнить ровно столько же, иначе будут случаи, когда вы не сможете отсортировать массив с определенным набором данных. В случае предсказания переходов, у вас будет просто более эффективно использоваться конвеер. А поскольку следующий шаг алгоритма вы не сможете выполнить не выполнив предыдущий (не изменяя сам алгоритм сортировки), то все, что вы получите (в случае пузырька) это уменьшение C в выражении C*f(n^2)

В общем случае — тот же самый. Обычно, если алгоритм полиномиальный к примеру, его не получится просто путем оптимизации железа сделать квазилинейным. Посмотрите пример пузырька в статье, там показано, что даже увеличив кол-во процессоров, при данном алгоритме, сложность останется O(n^2). Если у вас какое-то специфическое железо, под него нужен специфический алгоритм, чтобы работать быстро.

Почти в любом случае лучше тот алгоритм, у которого меньше класс сложности. Как упомянуто в статье, даже на самом быстром компьютере, если у вас сложность O(n*n!) или если вы совсем не везучий — O(2^n) в общем случае ваша программа будет работать дольше, чем не очень быстрый компьютер с алгоритмом O(n*log(n)).

Комбинирование разных алгоритмов сортировки является вполне нормальной и часто применяемой техникой, которая действительно дает хорошие результаты. Если взять пример немного по-проще вашего, то вполне нормально до некоторого не очень большого N применять все ту же всеми любимую сортировку пузырьком, а в случаях когда N становится большим переходить на quicksort.

Спасибо

На счет поразрядной сортировки и O(n) я уже отвечал выше в камментах. То, что существуют алгоритмы хуже O(n^2) (n*n! в вашем примере) я не сомневаюсь, но такие алгоритмы обычно на практике не применяются из-за своей малой эффективности.

Спасибо за критику. Другие алгоритмы обязательно будут рассмотрены в продолжении статьи про Ω(g(n)), Θ(g(n)).

Пожалуйста, я рад, что вам понравилось. В скором времени планирую написать продолжение про Ω(g(n)), Θ(g(n)) которые я в этой статье не рассматривал.

Да, уже заменил, еще раз спасибо

Спасибо, за то, что нашли ошибку, должно быть действительно «c*g(n) >= f(n)».
На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.

На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.

про квазилинейный рост, спасибо, поправлю

Как я понимаю, речь идет о сортировка выбором. Ее тоже можно рассматривать как пример O(n^2) алгоритма.

Я с вами согласен, что это нужно знать, но вот про то, что все, кто программирует знают это — думаю слишком сильное заявление :)

Я думаю вы правы, но статья ведь не об O(N) как таковом, а о том, что такое верхняя граница сложности алгоритма, как можно ее найти в общем случае и как ее применять чтобы определить хорошо или плохо рабобтает некий код.

Хорошее замечание.

Вы правы, можно но это уже будут не comparison алгоритмы.
Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.

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

Да уже сделал