# Chapter 2

## Exercise 2.1-1

<figure><img src="https://1997161-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FlBSM5MLFKTKipGIIw1fs%2Fuploads%2FeSLbckWWFdpKHHwxtB76%2Fexercise2-1-1.svg?alt=media&#x26;token=ebd8ad27-1465-4628-ac5c-cbab4db73462" alt=""><figcaption></figcaption></figure>

## 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

<figure><img src="https://1997161-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FlBSM5MLFKTKipGIIw1fs%2Fuploads%2F4VxWKxrDmKBiLMycDVRR%2Fexercise2-3-1.svg?alt=media&#x26;token=79a986b2-41f5-47fe-a70a-5908c1ac7d34" alt=""><figcaption></figcaption></figure>

## 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](https://en.wikipedia.org/wiki/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.**