Chapter 2

Exercise 2.1-1

Exercise 2.1-2

Available in the latest revision of the IM.

Exercise 2.1-3

Available in the latest revision of the IM.

Exercise 2.1-4

Available in the latest revision of the IM.

Exercise 2.1-5

Available in the latest revision of the IM.

Exercise 2.2-1

Available in the latest revision of the IM.

Exercise 2.2-2

Available in the latest revision of the IM.

Exercise 2.2-3

Available in the latest revision of the IM.

Exercise 2.2-4

Available in the latest revision of the IM.

Exercise 2.3-1

Exercise 2.3-2

Available in the latest revision of the IM.

Here is an alternative proof that relies on the properties of the divide step, as explained in the book on page 38. In the initial cal we have $p \le r$. Any call with this condition satisfied cannot lead to a subsequent recursive call with $p>r$ for the following reasons:

• If $p=r$, then the procedure returns without making any further calls.

• Otherwise $p < r$ and the divide step computes the index $q$ that partitions $A[p:r]$ into two adjacent subarrays containing $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$ elements, respectively. None of these will be empty, since $n=r-p+1 \ge 2$. Consequently, both recursive calls will happen with $p \le r$.

Exercise 2.3-3

Available in the latest revision of the IM.

Exercise 2.3-4

Available in the latest revision of the IM.

Exercise 2.3-5

Available in the latest revision of the IM.

Exercise 2.3-6

Available in the latest revision of the IM.

Exercise 2.3-7

Available in the latest revision of the IM.

Exercise 2.3-8

Available in the latest revision of the IM.

Problem 2-1

Available in the latest revision of the IM.

Timsort is a superb case study, that illuminates many of the intricacies in developing a hybrid sorting algorithm, derived from merge sort and insertion sort.

Problem 2-2

Available in the latest revision of the IM.

Problem 2-3

Available in the latest revision of the IM.

Problem 2-4

Available in the latest revision of the IM.