Sort Stack using just an additional stack
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 =&gt; s
            case Push(top, pop) =&gt; 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)) =&gt; Push(top, insert(x, pop))
            case _ =&gt; 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))))