Сортировка без использования разделяй и властвуй менее чем за n * n раз

Question

Рассмотрим следующий вход: 8,4,15,9,32,44,55

Предложите алгоритм для сортировки по возрастанию менее чем за n * n сложности Без использования подхода «разделяй и властвуй»

Answer 1

Для сравнительно небольших целых чисел, таких как эти, вы можете использовать сортировку по сегментам или сортировку по основанию , это будет O(n) и не делится и не захватывает.

Для больших целых чисел это все еще возможно, но сортировка ведра будет занимать слишком много места, а радикальная сортировка будет O(n*d), где d - количество цифр в наибольшем числе.