Order a stack with another auxiliary stack implementation and analyze

This algorithm is to order a stack(s_a) with another auxiliary stack(s_h). The basic thinking is pop x from s_a, and push it to s_h. Pop s_h and push to s_a until top of s_h is less than x. When s_a is empty, push all element from s_h and push to s_a by order.

After that, the data in s_a will be in decrease-order.

Pesudo code like below:

while not s_a.empty():           #---- 1
    x = s_a.pop()
    while not s_h.empty() and s_h.peek() < x:        #---- 2
        s_a.push(s_h.pop())
    s_h.push(x)

while not s_h.empty():
    s_a.push(s_h.pop())

In the extrem case, when element in s_a is in reverse order, the number of loop condition 1 is about n^1.82 while loop condition 2 is about n So, T(n) = O(n^2.82)

Really low performance. On my machine, sort 1000 element took about 5.11 second is extrem case, and 2.5 seconds in general case.

While use insert-sorting with O(n^2) just take 0.098 seconds to sort 1000 datas.