Как избавиться от StackOverFlow при рекурсивной сортировке?

Question

[NoMoneyException]

Как при помощи рекурсивной quick sort отсортировать массив из, например, 10^6 элементов? Я так понимаю, заканчивается память потока, и он выдает исключение. Как с этим в Java борются, или просто используют другую сортировку?

Answer 1

[Андрей]

Для этого используется паттерн "трамплин". Есть хороший пример реализации на StackOverflow (увы, текст на английском):

stackoverflow.com/a/32909860/1293168

Answer 2

[Станислав Макаров]

Не обязательно в качестве "стека" использовать системный стек вызовов. Вы можете вместо рекурсии использовать цикл, а вместо системного стека вызовов использовать стек в библиотеке вашего языка программирования. Вместо рекурсивного вызова у вас будет помещение кортежа значений - параметров сортировки - на стек и их извлечение оттуда на очередном шаге обработки.