Здравствуйте, MTD, Вы писали:

MTD>Моя очередь немного поныть

MTD>На днях ответил на вопросы на сайте Яндекса ...

MTD>Начало. С ходу предложили отсортировать массив целых положительных чисел. Сказал, что не буду изобретать ничего, а возьму std::sort, если сортировать надо часто подумаю о более подходящем алгоритме и структурах данных. Если сортировать надо много и набор данных специфический изучу вопрос и подберу подходящий метод сортировки. Посмотрели разочарованно. Поинтересовались что внутри std::sort, ответил, что скорее всего quick sort. Спросили про его сложность, сказал, что O(n * log n) и O(n * n) на уже упорядояенном массиве. Попросили рассказать как он работатет. Рассказал в общих чертах, что делится массив на 2 части, затем рекурсивно повторяется алгоритм к двум частям и т.д. до конца. Снова посмотрели разочарованно.

MTD>...

Есть только один православный алгоритм сортировки — heapsort. Все остальные методы — говно.
Ибо всегда сортирует за O(n*Log(n)) и требует ровно O(1) памяти, т.к. сортирует внутри самого массива.