> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-i-foundations/2.-getting-started.md).

# 2. Getting Started

## Exercises

### 2.1-1

<figure><img src="/files/jmk2AF0SworUmWwmoIKG" alt=""><figcaption></figcaption></figure>

### 2.1-2

**Available in the latest revision of the IM.**

### 2.1-3

**Available in the latest revision of the IM.**

### 2.1-4

**Available in the latest revision of the IM.**

### 2.1-5

**Available in the latest revision of the IM.**

### 2.2-1

**Available in the latest revision of the IM.**

### 2.2-2

**Available in the latest revision of the IM.**

### 2.2-3

**Available in the latest revision of the IM.**

### 2.2-4

**Available in the latest revision of the IM.**

### 2.3-1

<figure><img src="/files/HeA8pPADlAVbfmKMcV2Q" alt=""><figcaption></figcaption></figure>

### 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. Initially, 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$$.

### 2.3-3

**Available in the latest revision of the IM.**

### 2.3-4

**Available in the latest revision of the IM.**

### 2.3-5

**Available in the latest revision of the IM.**

### 2.3-6

**Available in the latest revision of the IM.**

### 2.3-7

**Available in the latest revision of the IM.**

### 2.3-8

**Available in the latest revision of the IM.**

## Problems&#x20;

### 2-1 Insertion sort on small arrays in merge sort

**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.

### 2-2 Correctness of bubblesort

**Available in the latest revision of the IM.**

### 2-3 Correctness of Horner’s rule

**Available in the latest revision of the IM.**

### 2-4 Inversions

**Available in the latest revision of the IM.**