Напишите функцию ManualSort, которая сортирует слайс строк по возрастанию
на месте, без пакетов sort и slices. Строки сравниваются обычным
оператором < (лексикографически по байтам).
// ManualSort сортирует items по возрастанию на месте.
func ManualSort(items []string)
Пример
items := []string{"m", "q", "b", "z", "c", "a"}
ManualSort(items)
fmt.Println(items) // [a b c m q z]
Ограничения
0 ≤ len(items) ≤ 3·10⁵, строки до 20 байт, возможны повторы и пустые строки.- Ожидается O(n log n): квадратичные сортировки (пузырёк, вставки, выбор) не
пройдут по времени. Обратите внимание на «неудобные» входы: уже отсортированный,
отсортированный в обратном порядке и слайс из одинаковых строк — на них
наивный quicksort тоже деградирует до O(n²).
- Устно: какую сортировку выбрали, почему, устойчива ли она, сколько памяти ест.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.