Sort Stack using just an additional stack

Question

The problem is from the cracking coding Interview programming book.

The problem is that:

Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array).

Below is my code in scala to sort Stack s, however, I think it is not the optimal solution in scala, may I know any other solutions can be written in functional programming language scala.

import scala.collection.mutable.Stack
    def sorted(s: Stack[Int]): Unit={
        def sortedwithtemp(original: Stack[Int], temp:Stack[Int], current: Int): Unit=(current, temp.top)match{
          case (a,b) if a>=b =>temp.push(a); 
          if(original.size==0) original.pushAll(temp)
          else {
            val curr= original.pop()
          sortedwithtemp(original, temp, curr) 
          }

          case (a,b) => original.push(temp.pop()); 
           if (temp.isEmpty) {temp.push(current); val curr= original.pop();sortedwithtemp(original, temp, curr)}
           else sortedwithtemp(original, temp, current)       
        }


        val tempstack=new Stack[Int]
        if (s.size>=2){
          tempstack.push(s.pop())
          val current=s.pop()
          sortedwithtemp(s, tempstack, current)
        }
   }

Answer 1

It's easier if you define your own Stack type, as the Scala Stack is a collection type which makes it a bit heavyweight.

A stack is either an Empty stack or an element (top) pushed onto a stack (pop):

// Define a simple immutable stack datatype.
trait Stack[+T]
object Empty extends Stack[Nothing]
case class Push[+T](top : T, pop : Stack[T]) extends Stack[T]

We can sort a stack by inserting each element onto a sorted stack. The insertion is done by popping the stack until we find the right position, and then rebuilding the stack when the call-stack returns.

object StackSort {
    // Sort a stack using insertion-sort.
    def sort[T](s : Stack[T])(implicit ord : Ordering[T]) : Stack[T] =
        s match {
            case Empty => s
            case Push(top, pop) => insert(top, sort(pop))
        }

    // Insert an element into a sorted stack.
    def insert[T](x : T, s : Stack[T])(implicit ord : Ordering[T]) : Stack[T] =
        s match {
            case Push(top, pop) if (ord.lt(x, top)) => Push(top, insert(x, pop))
            case _ => Push(x, s)
        }
}

A simple test:

object Test {
    import StackSort._

    def main(args : Array[String]) : Unit = {
        val test = Push(3, Push(1, Push(2, Push(5, Empty))))
        println(test)

        val sorted = sort(test)
        println(sorted)
    }
}

which outputs:

Push(3,Push(1,Push(2,Push(5,Empty$@45c8e616))))
Push(5,Push(3,Push(2,Push(1,Empty$@45c8e616))))