The sort operation arranges stack elements in some order. For example, consider the following:

[ 11, [ 29, [ 5, [ 17, [ ] ] ] ] ]

Here is the result of sorting the stack in ascending order:

[ 5, [ 11, [ 17, [ 29, [ ] ] ] ] ]

Sorting is one of the most useful collection operations. Here are some examples of problems that are solved by sorting:

Problem	Solution
Find books at a library.	Sort library books by the title or the author's name.
Find cheap sweaters.	Sort sweaters by price in ascending order.
Find the 5 tallest mountains in the world.	Sort mountains by elevation in descending order.

Next, let's discuss how sorting works. There are great many ways to sort, but here is one simple way to sort in ascending order:

1. Write down an empty "sorted" stack which will contain the numbers in order.
2. Find the maximum number in the original stack and pop it from the stack.
3. Push this maximum number into the "sorted" stack.
4. Repeat steps 2 and 3 until the original stack is empty.

Let's use this algorithm to sort:

[ 11, [ 29, [ 5, [ 17, [ ] ] ] ] ]

Here is a video demonstration:

And here is a table view:

Step	Stack	Maximum Value	Maximum Index	"Sorted" Stack
1	[ 11, [ 29, [ 5, [ 17, [ ] ] ] ] ]	29	1	[ ]
2	[ 11, [ 5, [ 17, [ ] ] ] ]	17	2	[ 29, [ ] ]
3	[ 11, [5, [ ] ] ]	11	0	[ 17, [ 29, [ ] ]
4	[ 5, [ ] ]	5	0	[ 11, [ 17, [ 29, [ ] ] ] ]

As we can see, the result of sorting [ 11, [ 29, [ 5, [ 17, [ ] ] ] ] ] = [ 5, [ 11, [ 17, [ 29, [ ] ] ] ] ]

By repeatedly pushing the maximum value to an empty stack, we ended up with a stack that contains the smallest value at the top and the largest value at the bottom.

This algorithm is called the Selection Sort.

Now let's try to more precisely describe Selection Sort.

We need to keep track of the "sorted" stack, so we first convert the sort operation to the sort_compute function, whose input is the original stack and the current sorted stack, and the output is the fully sorted stack.

We can convert the expression as follows:

Result of sorting s = output of function sort_compute where input stack is s and the sorted stack is [ ]

Notice that the sorted stack is initially empty.

Next, suppose that:

• max = maximum of [ x, y ]
• idx = index of max in [ x, y ]

Then:

output of function sort_compute where input stack is (result of removing index idx from stack [ x, y ]) and the sorted stack is [ max, c ]

Notice that the stack is [ x, y ] rather than a single variable. If the stack was a single variable, then the stack could be empty. But we want the stack to have at least 1 element, so we use a 2-element list.

Output of function sort_compute where input stack is [ ] and the sorted stack is c = c

Let's use the above properties to evaluate:

Result of sorting [ 248, [ 2150, [ 1400, [ ] ] ] ]

First, we convert the expression to the sort_compute function:

output of function sort_compute where input stack is [ 248, [ 2150, [ 1400, [ ] ] ] ] and the sorted stack is [ ]

Next, let:

• max = the maximum of [ 248, [ 2150, [ 1400, [ ] ] ] ]
• idx = index of max in [ 248, [ 2150, [ 1400, [ ] ] ] ]

Then we claim that:

output of function sort_compute where input stack is (result of removing index idx from stack [ 248, [ 2150, [ 1400, [ ] ] ] ]) and the sorted stack is [ max, [ ] ]

Since:

The maximum of [ 248, [ 2150, [ 1400, [ ] ] ] ] = 2150

We claim that:

max = 2150

And:

The index of 2150 in [ 248, [ 2150, [ 1400, [ ] ] ] ] = 1

So we conclude that:

idx = 1

Using substitution, we claim that:

output of function sort_compute where input stack is (result of removing index 1 from stack [ 248, [ 2150, [ 1400, [ ] ] ] ]) and the sorted stack is [ 2150, [ ] ]

We know that:

The result of removing index 1 from stack [ 248, [ 2150, [ 1400, [ ] ] ] ] = [ 248, [ 1400, [ ] ] ].

Using substitution, we can claim that:

output of function sort_compute where input stack is [ 248, [ 1400, [ ] ] ] and the sorted stack is [ 2150, [ ] ]

Now we can begin another cycle. Let:

• max = the maximum of [ 248, [ 1400, [ ] ] ]
• idx = index of max in [ 248, [ 1400, [ ] ] ]

Then we claim that:

output of function sort_compute where input stack is (result of removing index idx from stack [ 248, [ 1400, [ ] ] ]) and the sorted stack is [ max, [ 2150, [ ] ] ]

We know that the maximum of [ 248, [ 1400, [ ] ] ] = 1400, so we conclude that max = 1400.

Then we claim that the index of max in [ 248, [ 1400, [ ] ] ] = 1. Therefore, idx = 1.

Using substitution, we claim that:

output of function sort_compute where input stack is (result of removing index 1 from stack [ 248, [ 1400, [ ] ] ]) and the sorted stack is [ 1400, [ 2150, [ ] ] ]

We also know that:

result of removing index 1 from stack [ 248, [ 1400, [ ] ] ] = [ 248, [ ] ]

Using substitution, we claim that:

output of function sort_compute where input stack is [ 248, [ ] ] and the sorted stack is [ 1400, [ 2150, [ ] ] ]

There's just 1 more element left. Since there is just 1 element left, we can just pop it and push it into the sorted stack. But since we did not specify such a property, let's go ahead and use the sorting property again. Let:

• max = the maximum of [ 248, [ ] ]
• idx = index of max in [ 248, [ ] ]

output of function sort_compute where input stack is (result of removing index idx from stack [ 248, [ ] ]) and the sorted stack is [ max, [ 1400, [ 2150, [ ] ] ] ]

Since there is just 1 element, we are going to skip a few steps and make the following claims:

1. max = 248
2. idx = 0
3. (result of removing index idx from stack [ 248, [ ] ]) = [ ]
4. [ max, [ 1400, [ 2150, [ ] ] ] ] = [ 248, [ 1400, [ 2150, [ ] ] ] ]

Using substitution, we claim that:

output of function sort_compute where input stack is [ ] and the sorted stack is [ 248, [ 1400, [ 2150, [ ] ] ] ]

Then we claim that:

output of function sort_compute where input stack is [ ] and the sorted stack is [ 248, [ 1400, [ 2150, [ ] ] ] ] = [ 248, [ 1400, [ 2150, [ ] ] ] ]

Now use the Transitive Property several times to conclude that:

The result of sorting [ 248, [ 2150, [ 1400, [ ] ] ] ] = [ 248, [ 1400, [ 2150, [ ] ] ] ]

Another Way To Find Minimum and Maximum

Notice that when we sort a collection in increasing order, the first element in the collection is the minimum value, and the last element in the collection is the maximum value. Thus, when we sort, we get the minimum and maximum values for free. But the sort operation requires more time to compute than the minimum or maximum operations because the sort operation consists of many maximum operations. Thus, we usually don't sort just to find the minimum or maximum value.