Using a Stack

To speed things up, what we can do is use an auxiliary data structure that helps us keep track of comparisons. Why don't we use a stack?

With a stack, instead of nested loop, we can do one pass instead. This is done by using the follow pseudocode:

Step 1 Push the first element to the stack.