Пусть задан файл l, состоящий из записей:

Припишем каждой записи l(j) некоторый признак, или, по-другому, ключ K_l(j) (j = 1, 2, ..., n). Обычно ключ - это какое-либо отдельное поле или комбинация полей записи. Будем считать, что на множестве ключей задано отношение линейного порядка или следования с обычными свойствами. Иными словами, элементы этого множества можно выстроить в порядке неубывания (невозрастания).

Задача сортировки файла ставится так. Найти такую перестановку записей (1):

чтобы их ключи располагались в неубывающем порядке:

K_m(1) £ K_m(2) £ ... £ K_m(n).

При решении научных и технических задач довольно часто запись целиком составляет поле ключа. Для получения из (1) файла (2), вообще говоря, требуется физическое перемещение записей в памяти компьютера. Во многих случаях нет надобности реально формировать перестановку (2). Достаточно описать её тем или иным способом так, чтобы обеспечить непосредственный доступ к записям (1) в соответствии с порядком следования их ключей. Сделать это можно по-разному, например составлением списка индексов (адресов) элементов (2) в файле (1). Построение для (1) такого списка называют или индексированием, или адресным кодированием, или адресной сортировкой. Часто индексирование применяется в качестве первого этапа для обычной сортировки, то есть получения перестановки (2).

Пример. В таблице 1 приведен файл из 8 записей. Каждая из них относится к конкретному студенту, имеющему задолженность по какому-либо предмету. Запись состоит из 5 отдельных полей: номер, фамилия и инициалы, курс, предмет и тип задолженности. Индексирование данного файла в алфавитном порядке фамилий студентов осуществляется построением списка: 6, 2, 5, 3, 7, 8, 1, 4. Цифра 6 здесь указывает на первую запись (Балаганов Ш.), 2 - на вторую запись (Бендер О. И.) и т.д. 1 - на последнюю запись (Паниковский М. С.) отсортированного по фамилиям файла “Задолжники”. При необходимости список (6, 2, 5, 3, 7, 8, 1, 4) можно использовать для реального перемещения соответствующих записей в этом файле.

Таблица 1

 Иногда конкретный файл приходится сортировать одновременно по нескольким ключам.

Традиционно различают внутреннюю сортировку, обрабатывающую данные в оперативной памяти, и внешнюю сортировку, оперирующую с данными, находящимися на дисках. Проблемы оптимизации существенно различаются для этих случаев. При внутренней сортировке стараются уменьшить число сравнений ключей и перемещений записей файла. Во внешней сортировке решающим фактором эффективности соответствующего алгоритма становится количество обращений к дисковым устройствам.

В дальнейшем будем вести речь только о внутренней сортировке и рассматривать файлы, представляющие собой одномерные числовые массивы-векторы. Записями и ключами таких файлов будем считать значения соответствующих элементов массивов. Это не является каким-либо существенным ограничением. Дело в том, что обсуждаемые алгоритмы легко переносятся и на другие случаи внутренних сортировок.

Если под классификацией алгоритмов решения какой-либо конкретной проблемы понимать разбиение их по какому-либо признаку или группе признаков на именованные непересекающиеся подмножества, то следует признать, что для задачи сортировки массивов точной классификации не существует. Тем не менее по устоявшейся традиции все многообразные методы сортировок подразделяются на три основные группы: сортировки выбором, сортировки включениями и обменные сортировки [34; 36, c.135-190; 43, c.7-147]. Это разделение проводится по доминированию в соответствующем алгоритме типа действия: выбор, включение или обмен. Ниже будут рассмотрены следующие три медленных алгоритма сортировок: простым выбором, простыми включениями и простыми обменами (метод пузырька), а также три более эффективных алгоритма сортировок: слияниями, пирамидальная и быстрая. Первые из них для больших массивов имеют плохие временные характеристики и потому в практическом плане представляют собой лишь исторический интерес. Их трудоемкость равна O(n²) операций сравнений и обменов, где n - длина сортируемого массива. 
Сортировка слияниями и пирамидальная сортировка имеют трудоемкость O(n×log₂(n)) операций. Быстрая сортировка, хотя и имеет в худшем случае трудоемкость O(n²), в подавляющем большинстве реальных задач дает лучшие временные характеристики по сравнению с другими методами.