Сортировка стопки в возрастающем порядке?

Каков наилучший метод сортировки стека в порядке возрастания? Я наткнулся на этот вопрос интервью и столкнулся с некоторыми проблемами, чтобы найти лучшее и наиболее эффективное решение.

Я могу придумать два метода.

1. Чтобы извлечь все содержимое стека и сохранить его в массиве, затем отсортировать массив в
   O (nLog n) , а затем вернуть содержимое в стек. Не лучший способ ....

2. Выполните рекурсивную реализацию стека для его сортировки

void sort(stack)
{
    type x;

    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }           
}

void insert(x, stack)
{
    type y;

    if (!isEmpty(stack) && top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } 
    else {
        push(x, stack);
    }
} 

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

Можно ли решить эту проблему гораздо лучшим способом с наилучшей пространственно-временной сложностью?

Существует так много рекурсивных вызовов (перекрывающихся подзадач), является ли это претендентом на решение задач типа динамического программирования ?

Каким будет лучший способ решить эту проблему? ?