How to sort a stack using only stack operations?

It can be done recursively using the same stack. O(n^2) I have coded it in C++ but the conversion to C is trivial. I just like templates and you did tag your question as C++

template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
  if(element > stack.Top())
  {
    T top = stack.Pop();
    Insert(element, stack);
    stack.Push(top);
  }
  else
  {
    stack.Push(element);
  }
}

template<typename T>
void StackSort(Stack<T>& stack)
{
  if(!stack.IsEmpty())
  {
    T top = stack.Pop();
    StackSort(stack);
    Insert(top, stack);    
  }    
}

Given those stack operations, you could write a recursive insertion sort.

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); 
    }
}

Assuming that the only data structure allowed here is the Stack, then you could use 2 Stacks.

Iterate until the original stack is empty and in each iteration, pop an element from the original stack, while the top element in the second stack is bigger than the removed element, pop the second stack and push it to the original stack. Now you can push the element you originally popped off the original stack to the second stack.

The time complexity of this approach is O(N^2).

C code to implement this algorithm would be (excuse my rusty C skills):

void SortStack(struct Stack * orig_stack)
{
  struct Stack helper_stack;
  while (!IsEmpty(orig_stack))
  {
    int element = Pop(orig_stack);
    while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
    {
      Push(orig_stack, Pop(&helper_stack));
    }
    Push(&helper_stack, element);
  }
  while (!IsEmpty(&helper_stack))
  {
    Push(orig_stack, Pop(&helper_stack));
  }
}