# Sort Stack using just an additional stack

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)
}
}

• You can compare to this version of 2 stack sort . The problem statement is not quite right, you need to be able to move 1 element to a local variable in order to be able to manipulate the stacks in order to "move" that element. Commented Dec 7, 2016 at 9:13
• @rcgldr, I use current as the local variable to store, pls check, thanks Commented Dec 7, 2016 at 9:17
• Using current as the local variable is OK. My point was that the problem statement is faulty, not your code. Commented Dec 7, 2016 at 9:18
• problem statement I just copy from the book, and my main concern is how to improve it as scala is the functional programming :( Commented Dec 7, 2016 at 9:19
• With just 2 stacks, the time complexity is O(n^2), and similar to insertion sort. You pop off an element, then move the stacks to find where to insert the element, move the stacks back, then repeat the process until the stack is sorted. With 3 stacks, the sort can be done in O(n log(n)), using merge sort or better still polyphase merge sort (almost no one knows polyphase sort anymore). Commented Dec 7, 2016 at 9:26

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))))