Я попытался ответить на это с помощью внешней сортировки, но интервьюер ответил, что сложность была слишком высокой n.n (log (n)), т.е. n квадрат * logn. Есть ли лучшая альтернатива.

Чтобы упростить вопрос: предположим, у нас есть 1000 элементов для сортировки с пространством, выделенным только для 100 элементов. Какой самый лучший алгоритм, который займет меньше времени, чем внешняя сортировка.