2. Внутренняя сортировка
 

Основными требованиями к алгоритмам сортировки, как и ко всяким алгоритмам, являются требования по памяти и по времени выполнения. Это предполагает, что сортировка элементов массива выполняется на месте, без передачи их в результирующий массив. Хорошей мерой эффективности алгоритма по времени могут быть число необходимых сравнений ключей С и число пересылок М, которые зависят от числа элементов n.

Самыми простыми методами сортировки являются так называемые прямые методы, они требуют порядка О(n² ) сравнений ключей. Быстрые (улучшенные) методы сортировки в самом благоприятном случае требуют порядка O(n*log₂n) сравнений, имеются многочисленные варианты прямых и быстрых методов сортировки.

Прямые методы сортировки, не требующие дополнительной памяти, можно разбить на три категории:

• сортировка методом прямого включения;
• сортировка методом прямого выбора;
• сортировка методом прямого обмена (сортировка методом пузырька).