Sort List Property

result of sorting [ el, rem ] with sorted stack sl = result of sorting (remaining elements after [ el, rem ] is popped at index (index of the maximum value in stack [ el, rem ])) with sorted stack [ maximum value in stack [ el, rem ], sl ]

This property has many parts, so let's break it down. Another way to look at this property is:

(result of sorting [ el, rem ] with sorted list sl) = (result of the sorting step)

This says that sorting the list [ el, rem ] with sorted list sl is equivalent to the complicated sorting operation on the right. And what is the right side doing? As before, we look at the innermost operation first, which is

index of the maximum value in list [ el, rem ]

So we first find the maximum index of the list.

The parent operation is:

remaining elements after [ el, rem ] is popped at index (...)

So we pop the list at the maximum index we just calculated.

The "sorted list" is also updated. We push the maximum value into the "sorted list."

Effectively, we popped the maximum value from the original list and pushed it into the "sorted list."

Examples

result of sorting [ 7, [ 5, [ ] ] ] with sorted stack [ ] = result of sorting (remaining elements after [ 7, [ 5, [ ] ] ] is popped at index (index of the maximum value in stack [ 7, [ 5, [ ] ] ])) with sorted stack [ maximum value in stack [ 7, [ 5, [ ] ] ], [ ] ]

result of sorting [ 1, [ 4, [ 3, [ 2, [ ] ] ] ] ] with sorted stack [ ] = result of sorting (remaining elements after [ 1, [ 4, [ 3, [ 2, [ ] ] ] ] ] is popped at index (index of the maximum value in stack [ 1, [ 4, [ 3, [ 2, [ ] ] ] ] ])) with sorted stack [ maximum value in stack [ 1, [ 4, [ 3, [ 2, [ ] ] ] ] ], [ ] ]

result of sorting [ 248, [ 2150, [ 1400, [ ] ] ] ] with sorted stack [ 3305, [ ] ] = result of sorting (remaining elements after [ 248, [ 2150, [ 1400, [ ] ] ] ] is popped at index (index of the maximum value in stack [ 248, [ 2150, [ 1400, [ ] ] ] ])) with sorted stack [ maximum value in stack [ 248, [ 2150, [ 1400, [ ] ] ] ], [ 3305, [ ] ] ]

In the first example, we are sorting [7,[5,[]]]. First, we find the maximum value and index, which are 7 and 0, respectively. Now, we pop at index 0, and push 7 into the "sorted list." Thus, at the conclusion of this step, the original list is now

[5, []]

and the "sorted list" is

[7, []]

Now let's take a look at the last example. We want to sort

[ 248, [ 2150, [ 1400, [ ] ] ] ]

and the "sorted list" is

[ 3305, [ ] ]

We can see that 3305 was previously pulled from the original list and pushed into the "sorted list." Running the sorting step again, we find the maximum value in the remaining list, which is 2150. We then pop this and push it into the "sorted list." Then the remaining list is:

[ 248, [ 1400, []]]

And the "sorted list" is

[2150, [3305, []]]

We can see that the "sorted list" is starting to look like a sorted version of the original list.

Comments

Please log in to add comments