Назовите две-три сортировки, их названия и сложность

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

Держите ли вы в голове базовую таблицу сложностей и понимаете ли, что у сортировки есть не только время, но и память со стабильностью. Для Go смотрят отдельно: знаете ли вы, что руками сортировки писать не нужно, в стандартной библиотеке уже лежит готовая.

Как отвечать

Назовите три и сразу с характеристиками.

Быстрая сортировка: в среднем O(n log n), в худшем O(n²) при неудачном выборе опорного элемента, память O(log n) на стек рекурсии, нестабильная. Сортирует на месте, поэтому на практике выигрывает по константе.

Сортировка слиянием: O(n log n) во всех случаях, память O(n) под дополнительный буфер, стабильная. Её берут, когда нужна гарантия по времени или сохранение порядка равных элементов.

Пузырёк: O(n²) в среднем и худшем, O(n) на уже отсортированных данных, но только если есть флаг ранней остановки. Память O(1). Называть её стоит как учебный пример, а не как рабочий вариант.

Для Go добавьте практику:

slices.Sort(nums)
slices.SortFunc(items, func(a, b Item) int { return cmp.Compare(a.Age, b.Age) })

sort.Slice и slices.Sort внутри используют гибрид на базе быстрой сортировки, который переключается на пирамидальную при плохом разбиении, поэтому квадратичного худшего случая там нет. Стабильные версии это sort.SliceStable и slices.SortStableFunc.

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

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

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

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