как отсортировать очередь, используя (просто) другую очередь и некоторые переменные, менее чем за O (n ^ 2)?

Question

Как я могу отсортировать очередь размера N, используя только другую очередь размера N и конечное число переменных?

Наивная реализация - найти минимум очереди и поместить его в пустую очередь, затем найти новый минимум и отправить его и т. Д. - O (n ^ 2) Есть ли более эффективный алгоритм?

Answer 1

Попробуйте Сортировка слиянием , то есть O (n log n)