Как реализовать сортировку данных

Что проверяют

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

Как отвечать

С Go 1.21 основной инструмент это пакет slices, старый sort остаётся для унаследованного кода.

slices.Sort(nums)                       // для упорядоченных типов
slices.SortFunc(people, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)    // отрицательное, ноль, положительное
})
slices.SortStableFunc(people, byAge)
i, ok := slices.BinarySearch(nums, 42)

Отличие от старого API существенное: у sort.Slice компаратор возвращает bool в смысле «меньше», у slices.SortFunc он возвращает int в стиле strcmp. Перепутать легко, а код при этом компилируется.

Сортировка по нескольким ключам собирается через cmp.Or (Go 1.22):

slices.SortFunc(rows, func(a, b Row) int {
    return cmp.Or(
        cmp.Compare(a.Dept, b.Dept),
        cmp.Compare(b.Salary, a.Salary), // по убыванию
    )
})

Свойства, которые стоит назвать:

• Алгоритм с Go 1.19 это pdqsort: гибрид быстрой сортировки с переключением на пирамидальную при плохом распределении и вставками на коротких участках. Худший случай O(n log n), деградации до квадрата на подобранных данных нет.
• Обычная сортировка неустойчива, порядок равных элементов не гарантирован. Нужна устойчивость, берите SortStableFunc: она платит дополнительной памятью и константой.
• sort.Slice работает через рефлексию и заметно медленнее дженерик-версии на тех же данных.
• Компаратор обязан задавать строгий порядок. Возврат true при равенстве в sort.Slice нарушает контракт и даёт непредсказуемый результат.
• cmp.Compare корректно обрабатывает NaN у чисел с плавающей точкой, а наивное сравнение через < на NaN ломает порядок.

Когда нужна своя реализация: данные не помещаются в память (внешняя сортировка со слиянием кусков), ключи целые в узком диапазоне (сортировка подсчётом или поразрядная, O(n)), либо нужны не все элементы, а top-K, и вместо сортировки берут кучу за O(n log k).

И общий ответ на «как сортировать данные»: если они пришли из базы, сортировать в базе по индексу, а не тянуть всё в приложение.

Где спотыкаются

Уходят в пересказ учебных алгоритмов, не называя slices.SortFunc, и не могут ответить, устойчива ли стандартная сортировка и что будет при некорректном компараторе.