Appendix 1
Solutions

Chapter 1

These are the solutions to the .

1. Here’s what the breakdown phase of Mergesort looks like for this example:

   

    

2. Here’s what the merging phase of Mergesort looks like for this example:

   

    

3. Here’s what the result of Mergesort looks like for this example:

   

   The interesting thing to note here is that for each integer, the timestamps remain sorted! For example, although we moved around the three instances of value 1 so that they’re now all in a row, their timestamps remain in their original order.

   Because of this, computer scientists refer to Mergesort as an example of a stable sort algorithm. A stable sort algorithm ensures that when there are duplicate instances of the same value, those two instances will remain in the same order (relative to each other) that they were before the sorting.

   Note that many sorting algorithms, including Quicksort, do not produce a stable sort. If stable sorting is important for your application, this may be reason enough to choose Mergesort over Quicksort.

4. As I mentioned in the exercise, there’s no right or wrong way of doing this, but here’s what I did. Here are my two loops, starting with the first version:

   ​	​for​ i ​in​ range(1, 11):
   ​	​print​(i)

   And here’s my second version:

   ​	x = 1
   ​	​while​ x < 11:
   ​	​print​(x)

   Here are the two sets of bytecode:

   ​	For loop:
   ​
   ​	1 0 LOAD_NAME 0 (range)
   ​	2 LOAD_CONST 0 (1)
   ​	4 LOAD_CONST 1 (11)
   ​	6 CALL_FUNCTION 2
   ​	8 GET_ITER
   ​	>> 10 FOR_ITER 12 (to 24)
   ​	12 STORE_NAME 1 (i)
   ​
   ​	2 14 LOAD_NAME 2 (print)
   ​	16 LOAD_NAME 1 (i)
   ​	18 CALL_FUNCTION 1
   ​	20 POP_TOP
   ​	22 JUMP_ABSOLUTE 10
   ​	>> 24 LOAD_CONST 2 (None)
   ​
   ​	While loop:
   ​
   ​	1 0 LOAD_CONST 0 (1)
   ​	2 STORE_NAME 0 (x)
   ​
   ​	2 >> 4 LOAD_NAME 0 (x)
   ​	6 LOAD_CONST 1 (11)
   ​	8 COMPARE_OP 0 (<)
   ​	10 POP_JUMP_IF_FALSE 22
   ​
   ​	3 12 LOAD_NAME 1 (print)
   ​	14 LOAD_NAME 0 (x)
   ​	16 CALL_FUNCTION 1
   ​	18 POP_TOP
   ​	20 JUMP_ABSOLUTE 4
   ​	>> 22 LOAD_CONST 2 (None)
   ​	24 RETURN_VALUE

   Both sets of bytecode seem to have the same number of instructions, and similar ones at that. However, they clearly aren’t exactly the same.

   For example, the for loop version has the FOR_ITER instruction, which appears to be specific to a for loop. The while loop version has unique instructions such as COMPARE_OP, which is needed to compare x to 11. This version also has a POP_JUMP_IF_FALSE command, which appears to terminate the loop if the expression x < 11 is false.