Напишите сортировку вставками. Она должна работать для любого типа элементов
с переданной функцией сравнения, сортировать на месте и быть устойчивой:
элементы, равные по less, сохраняют исходный относительный порядок. Пакеты
sort и slices для сортировки не использовать.
// InsertionSort сортирует a на месте по возрастанию согласно less.
// less(x, y) == true, если x должен стоять раньше y.
func InsertionSort[T any](a []T, less func(x, y T) bool)
Примеры
[5, 2, 4, 6, 1, 3] → [1, 2, 3, 4, 5, 6]
[] → []
по длине: ["bb", "a", "cc", "d", "eee"] → ["a", "d", "bb", "cc", "eee"]
(a раньше d, bb раньше cc — как во входе)
Ограничения
0 ≤ len(a) ≤ 10⁶; без дополнительных аллокаций памяти (O(1) доп. памяти).- На почти отсортированных данных (каждый элемент стоит не дальше нескольких
позиций от своего места) сортировка должна работать почти за O(n) — это
главное преимущество вставок, его проверяют на большом входе.
- Устно: начните с самого простого O(n²) варианта, затем расскажите, как его
ускорить.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.