Все простые алгоритмы имеют один фатальный недостаток — время их выполнения имеет порядок n². Это делает сортировку больших объемов данных очень медленной. По существу, в какой-то момент эти алгоритмы становятся слишком медленными, чтобы их применять. Конечно, это не означает, что функция f(n)=n² в какой-то точке возрастает скачкообразноно. Просто при увеличении размера массива n меняется характер сортировки, из внутренней она фактически становится внешней, когда массив не помещается в оперативной памяти и начинается интенсивная подкачка страниц, а за ней пробуксовывание механизма виртуальной памяти. Это действительно может наступить внезапно, и тогда окажется, что незначительное увеличение сортируемого массива или просто добавление какой-либо совершенно незначительной задачи приведет к катастрофическому увеличению времени сортировки (например в десятки раз!). К сожалению, страшные истории о "сортировках, которые продолжались три дня", зачастую реальны. Когда сортировка занимает слишком много времени, причиной этому обычно является неэффективность использованного в ней алгоритма. Тем не менее, первой реакцией в такой ситуации часто становится оптимизация кода вручную, возможно, путем переписывания его на ассемблере. Несмотря на то, что ручная оптимизация иногда ускоряет процедуру на постоянный множитель, если алгоритм сортировки не эффективен, сортировка всегда будет медленной независимо от того, насколько оптимально написан код. Следует помнить, если время работы процедуры пропорционально n² то увеличение скорости кода или компьютера даст лишь небольшое улучшение, поскольку время выполнения увеличивается как n². Действительно, чтобы увеличить в т раз размер сортируемого массива при сохранении времени сортировки, быстродействие процессора придется увеличить в n² раз при условии, что время доступа к элементам массива не увеличится, т.е. не уменьшится, например, эффективность подкачки страниц. Существует правило: если используемый в программе алгоритм слишком медленный сам по себе, никакой объем ручной оптимизации не сделает программу достаточно быстрой. Причем чем сложнее алгоритм, тем сложнее переписать его на Ассемблере и тем проще сделать в нем ошибку при переписывании, а тем более сложнее ее найти. Решение заключается в применении лучшего алгоритма сортировки.

Рассмотрим два улучшенных метода сортировки. Первый называется сортировкой Шелла. Второй — быстрая сортировка — обычно считается самым лучшим алгоритмом сортировки. Оба метода являются более совершенными способами сортировки и имеют намного лучшую общую производительность, чем любой из приведенных выше простых методов.