Можно ли отсортировать n целых чисел с амортизированной сложностью O (n)?

Теоретически возможно ли отсортировать массив из n целых чисел с амортизированной сложностью O (n)?

А как насчет попытки создать наихудший случай O (n)? ) сложность?

Большинство алгоритмов сегодня построены на O (nlogn) среднем + O (n ^ 2) наихудшем случае. Некоторые, при использовании большего количества памяти, являются O (nlogn) наихудшими.

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