Стабильная сортировка и определённый порядок

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

Если источник — SQL-запрос без ORDER BY, файловый обход без сортировки или параллельный поток, начальный порядок может меняться. Стабильный алгоритм честно сохранит эту случайность. Для воспроизводимого результата нужен полный контракт: основной ключ, дополнительные ключи и правило разрешения равенства. Нередко последним ключом становится устойчивый уникальный идентификатор.

Порядок строк зависит от locale и collation. Байтовая сортировка в locale C удобна для повторяемой технической обработки, но не обязана совпадать с алфавитным ожиданием человека. Регистронезависимое сравнение, обработка ё и Unicode-нормализация тоже должны быть явно выбраны. Нельзя обещать «обычный алфавитный порядок» без определения этих условий.

GNU sort имеет собственные опции и поведение. В частности, стабильный режим отключает дополнительное сравнение всей строки при равенстве выбранных ключей. POSIX-реализация на другой системе может не поддерживать длинную опцию. Если инструкция использует GNU-флаг, укажите это рядом с командой, а не рассчитывайте, что название утилиты гарантирует одинаковый интерфейс.

Физическая строка CSV может быть только частью записи: quoted поле способно содержать перевод строки. Поэтому сортировка CSV утилитой sort без разбора структуры небезопасна. Сначала нужен парсер, затем сравнение значений полей, затем writer с согласованным диалектом. Для JSONL одна строка действительно соответствует записи, но сортировка текста всё равно не равна сортировке чисел.

Текстовые значения 2 и 10 в лексикографическом порядке идут иначе, чем целые числа. Даты со смешанными смещениями тоже нельзя надёжно сравнивать как строки. Приведение к типу должно предшествовать построению ключа. Ошибочное значение лучше отклонить с номером записи, чем молча поставить в произвольное место.

Слияние нескольких уже отсортированных частей требует одинакового правила сравнения во всех частях. Недостаточно, чтобы каждая команда называлась sort: настройки locale и обработка чисел тоже должны совпадать. Для равных ключей определите порядок источников и порядковый номер внутри источника, если важна история поступления. Сохраните эти признаки до объединения, потому что восстановить их после сортировки может быть невозможно. В SQL используйте полный ORDER BY при экспортном запросе и не полагайтесь на текущий план индекса. Добавление индекса способно поменять случайный порядок результата без изменения строк. Повторяемый экспорт начинается с определённого запроса, а стабильный текстовый writer лишь сохраняет уже выбранную последовательность записей.

Создайте выборку с одинаковыми основными ключами и разными вторичными. Добавьте строку в другом регистре, кириллицу и числа разной длины. Заранее запишите ожидаемый порядок идентификаторов. Такой тест обнаруживает ошибки контракта лучше, чем проверка на наборе из трёх уже отсортированных латинских слов.

Проверьте идемпотентность: второй запуск с теми же параметрами не должен менять выход. Затем перемешайте вход и выясните, должен ли итог остаться прежним. Если да, правила разрешения равенства обязаны быть достаточными. Если нет, исходный порядок — часть данных, и его нужно сохранять или записывать отдельным полем.

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