In this example, we prove that when we sort

[3,[2,[1,[]]]]

we get

[1, [2, [3, []]]]

First, we use the "Sort Begin Property" to initialize the "sorted list" to [ ]. Then we begin popping maximum values from the original list and pushing them into the "sorted list."

First, we pop 3 at index 0 and push it into the "sorted list." Step 9 shows that the remainig elements are now [2, [1, []]] and the "sorted list" is [3, []].

Then we pop 2 at index 0. Step 18 shows that the remainig elements are now [1, []] and the "sorted list" is [2, [3, []]].

Finally, we pop 1 at index 0. Step 25 shows that the remainig elements are now [ ] and the "sorted list" is [1, [2, [3, []]]].

Since the remaining list is now empty, the "sorted list" is the final result of the sorting operation.

Quiz (1 point)

Prove that:

result of sorting [ 3, [ 2, [ 1, [ ] ] ] ] = [ 1, [ 2, [ 3, [ ] ] ] ]

The following properties may be helpful:

result of sorting els = result of sorting els with sorted stack [ ]
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 ]
maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ] = 3
index of the maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ] = 0
remaining elements after [ 3, [ 2, [ 1, [ ] ] ] ] is popped at index 0 = [ 2, [ 1, [ ] ] ]
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 ]
maximum value in stack [ 2, [ 1, [ ] ] ] = 2
index of the maximum value in stack [ 2, [ 1, [ ] ] ] = 0
remaining elements after [ 2, [ 1, [ ] ] ] is popped at index 0 = [ 1, [ ] ]
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 ]
maximum value in stack [ x, [ ] ] = x
index of the maximum value in stack [ x, [ ] ] = 0
remaining elements after [ x, [ ] ] is popped at index 0 = [ ]
result of sorting [ ] with sorted stack sl = sl
if index of the maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ] = 0, then remaining elements after [ 3, [ 2, [ 1, [ ] ] ] ] is popped at index (index of the maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ]) = remaining elements after [ 3, [ 2, [ 1, [ ] ] ] ] is popped at index 0
if the following are true:
- a = b
- b = c
then a = c
if maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ] = 3, then [ maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ], [ ] ] = [ 3, [ ] ]
if the following are true:
- remaining elements after [ 3, [ 2, [ 1, [ ] ] ] ] is popped at index (index of the maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ]) = [ 2, [ 1, [ ] ] ]
- [ maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ], [ ] ] = [ 3, [ ] ]
then result of sorting (remaining elements after [ 3, [ 2, [ 1, [ ] ] ] ] is popped at index (index of the maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ])) with sorted stack [ maximum value in stack [ 3, [ 2, [ 1, [ ] ] ] ], [ ] ] = result of sorting [ 2, [ 1, [ ] ] ] with sorted stack [ 3, [ ] ]
if index of the maximum value in stack [ 2, [ 1, [ ] ] ] = 0, then remaining elements after [ 2, [ 1, [ ] ] ] is popped at index (index of the maximum value in stack [ 2, [ 1, [ ] ] ]) = remaining elements after [ 2, [ 1, [ ] ] ] is popped at index 0
if the following are true:
- a = b
- b = c
then a = c
if maximum value in stack [ 2, [ 1, [ ] ] ] = 2, then [ maximum value in stack [ 2, [ 1, [ ] ] ], [ 3, [ ] ] ] = [ 2, [ 3, [ ] ] ]
if the following are true:
- remaining elements after [ 2, [ 1, [ ] ] ] is popped at index (index of the maximum value in stack [ 2, [ 1, [ ] ] ]) = [ 1, [ ] ]
- [ maximum value in stack [ 2, [ 1, [ ] ] ], [ 3, [ ] ] ] = [ 2, [ 3, [ ] ] ]
then result of sorting (remaining elements after [ 2, [ 1, [ ] ] ] is popped at index (index of the maximum value in stack [ 2, [ 1, [ ] ] ])) with sorted stack [ maximum value in stack [ 2, [ 1, [ ] ] ], [ 3, [ ] ] ] = result of sorting [ 1, [ ] ] with sorted stack [ 2, [ 3, [ ] ] ]
if index of the maximum value in stack [ 1, [ ] ] = 0, then remaining elements after [ 1, [ ] ] is popped at index (index of the maximum value in stack [ 1, [ ] ]) = remaining elements after [ 1, [ ] ] is popped at index 0
if the following are true:
- a = b
- b = c
then a = c
if maximum value in stack [ 1, [ ] ] = 1, then [ maximum value in stack [ 1, [ ] ], [ 2, [ 3, [ ] ] ] ] = [ 1, [ 2, [ 3, [ ] ] ] ]
if the following are true:
- remaining elements after [ 1, [ ] ] is popped at index (index of the maximum value in stack [ 1, [ ] ]) = [ ]
- [ maximum value in stack [ 1, [ ] ], [ 2, [ 3, [ ] ] ] ] = [ 1, [ 2, [ 3, [ ] ] ] ]
then result of sorting (remaining elements after [ 1, [ ] ] is popped at index (index of the maximum value in stack [ 1, [ ] ])) with sorted stack [ maximum value in stack [ 1, [ ] ], [ 2, [ 3, [ ] ] ] ] = result of sorting [ ] with sorted stack [ 1, [ 2, [ 3, [ ] ] ] ]
if the following are true:
- a = b
- b = c
- c = d
then a = d
if the following are true:
- a = b
- b = c
- c = d
then a = d
if the following are true:
- a = b
- b = c
- c = d
then a = d
if the following are true:
- a = b
- b = c
then a = c

Please write your proof in the table below. Each row should contain one claim. The last claim is the statement that you are trying to prove.

Step	Claim	Reason (optional)	Error Message (if any)
1
2
3
4
5
6
7
8
9
10

Become a subscriber to save your progress, see the correct answer, and more!