Сортировки пузырьком, поскольку именно он и рассматривается в статье.
Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.
Операций вы должны будете выполнить ровно столько же, иначе будут случаи, когда вы не сможете отсортировать массив с определенным набором данных. В случае предсказания переходов, у вас будет просто более эффективно использоваться конвеер. А поскольку следующий шаг алгоритма вы не сможете выполнить не выполнив предыдущий (не изменяя сам алгоритм сортировки), то все, что вы получите (в случае пузырька) это уменьшение 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! в вашем примере) я не сомневаюсь, но такие алгоритмы обычно на практике не применяются из-за своей малой эффективности.
Спасибо, за то, что нашли ошибку, должно быть действительно «c*g(n) >= f(n)».
На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.
На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.
Я думаю вы правы, но статья ведь не об O(N) как таковом, а о том, что такое верхняя граница сложности алгоритма, как можно ее найти в общем случае и как ее применять чтобы определить хорошо или плохо рабобтает некий код.
Вы правы, можно но это уже будут не comparison алгоритмы.
Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.
В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.
Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.
На мой взгляд очень хорошая книга
По повоту «резрезать», не могли бы вы конкретно указать на ошибку в логике или выводах? Повторно сортировать ничего не предлагается.
На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.
На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.
Вы правы, можно но это уже будут не comparison алгоритмы.
Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.
В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.