Сортировки: порядок, устойчивость и цена преобразования

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

Устанавливаем порядок

Для целых значений порядок задаёт <. Для записи с датой и ID можно сравнивать дату, затем ID. Компаратор должен быть согласован: объект не меньше самого себя, отношение не противоречит себе, транзитивность сохраняется. Компаратор с внешним меняющимся счётчиком разрушает предусловие алгоритма.

Устойчивая сортировка сохраняет относительный порядок элементов, которые равны по выбранному ключу. Если сравниваем только дату, два разных ID с одинаковой датой остаются в исходной последовательности. Если добавили ID как второй ключ, они уже не равны по полному сравнению, и устойчивость не задаёт их прежний порядок.

Вставки для понимания инварианта

В сортировке вставками левый префикс уже отсортирован. Берём очередной элемент и сдвигаем большие значения вправо, освобождая место. После вставки отсортированный префикс увеличился на один.

func InsertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        x, j := a[i], i
        for j > 0 && a[j-1] > x {
            a[j] = a[j-1]
            j--
        }
        a[j] = x
    }
}

На уже отсортированном входе сдвигов нет, время Θ(n). На обратном порядке суммарно до n(n−1)/2 сдвигов, Θ(n²). Сравнение строго > не переставляет равные значения между собой. Память O(1), исходный вход изменяется.

Слияние независимых половин

MergeSort делит вход на две части, сортирует каждую и сливает два отсортированных потока. При слиянии сравниваем текущие головы и берём меньшую. Если значения равны, берём элемент левой половины, чтобы сохранить устойчивость.

Две отсортированные половины длины a и b объединяются за O(a+b). На каждом уровне разбиения суммарно обрабатывается O(n) элементов; уровней O(log n). Итоговое время O(n log n). В учебной реализации reference новые срезы возвращаются отдельно, исходный вход не изменяется. Пиковая дополнительная память O(n), общий объём выделений на всех уровнях может быть O(n log n). Это разные метрики.

Почему не одна сортировка на все случаи

QuickSort разделяет элементы вокруг выбранного опорного значения. Баланс разбиений определяет стоимость; плохие последовательные разбиения дают O(n²). Случайный выбор помогает ожидаемой оценке, но не отменяет существование плохого случая. HeapSort использует кучу и даёт O(n log n) в худшем случае при O(1) дополнительной памяти в обычной in-place модели, но типичные реализации не устойчивы.

Нижняя граница Ω(n log n) относится к общему сравнению различных ключей в модели сравнений. Counting sort использует дополнительные сведения: целочисленные ключи в диапазоне k. Время O(n+k), память зависит от k. Огромный диапазон для малого n может сделать её хуже.

Практика

Реализуйте InsertionSort и MergeSort. Проверяйте не только отсортированность: функция, вернувшая пустой массив, тоже формально не имеет инверсий. Сравните с независимым эталоном sort.Ints на копии. Проверьте пустой вход, повторы, отрицательные числа, обратный порядок и сохранение оригинала для MergeSort.

Для устойчивости используйте записи {Key, OriginalPosition} и сортируйте только по Key. После сортировки равные ключи должны иметь возрастающий OriginalPosition. Измерьте sorted и reversed отдельно. Практика — 60 минут.

Критерии готовности: множество элементов и повторения сохранены; порядок верен; договор изменения входа соблюдён; устойчивость проверяется на записях; оценены память результата и рабочая память.

Разбор

Два теста — «отсортировано» и «сохранено содержимое» — проверяют разные свойства. Стандартная библиотека полезна как тестовый эталон; в основном учебном решении она не заменяет реализацию изучаемого механизма. В прикладном коде обычно стоит использовать готовую сортировку, если нет особого требования.

Источники: Princeton: mergesort, quicksort, Go: sort.