Использует ли qsort кучную память?
Используя реализацию stdlib qsort() в VS2008.
Эта реализация qsort() использовать память в куче? Или используется только стековая память?
Решение
Быстрая сортировка — это алгоритм сортировки по месту. За исключением места в стеке времени выполнения для рекурсивных вызовов, он не использует память.
Другие решения
То, что он использует и что он не использует, является деталью реализации. Спецификация языка не дает никакого ответа на этот вопрос.
Хотя можно сказать, что есть нет причин для разумного qsort Реализация использовать динамическую память. Правильно реализованный план рекурсии в qsort никогда не потребует глубину рекурсии, которая больше, чем log2 максимального размера массива на данной платформе. Это означает, например, что на плоской платформе памяти глубина рекурсии не будет превышать «разрядность» платформы (например, она не ниже 32 на 32-битной платформе). Это в свою очередь означает, что qsort легко разрешает полностью основанную на стеке реализацию.