Chapter 2, Problem 1P

(a)

Program Plan Intro

To show that the insertion sort can sort the $n/k$ sub lists, each of length k in $\Theta \left(nk\right)$ time.

Explanation of Solution

The procedure of insertion sort in non-increasing order is as below:

INSERTION-SORT(A)

For $j=2$ to A .length

  $\text{key}=A\left[j\right]$

  $i=j-1$

while $i>0$ and $A\left[i\right]<\text{key}$

  $A\left[i+1\right]=A\left[i\right]$

  $i=i-1$

  $A\left[i+1\right]=\text{key}$

The j loop is running from 2 to the length of the array and then value in the index of array is stored in the key variable. After that the variable j is decreased by 1 and stored in the variable i.

Now, while loop is used in which two conditions are given: first condition is variable i is greater than 0 and the value of the array at index i must be less than key value.

The value at index i is swapped at the index $i-1$ . The variable i is decreased by 1 and the key value is stored at the index $i+1$ . The only change in the insertion sort of non-decreasing order to non-increasing order is flip the condition.

Analysis:

The worst case running time of the insertion sort to sort a list of length n is $\Theta \left(n^2\right)$ . Therefore, for sorting the $n/k$

sub lists of length k , the time taken by insertion sort is calculated as follows:

  $\Theta \left(k^2\cdot \frac{n}{k}\right)=\Theta \left(nk\right)$

Hence, the worst case running time of insertion sort to sort the $n/k$ sub lists, each of length k is $\Theta \left(nk\right)$ .

(b)

Program Plan Intro

To show that the worst case running time to merge the sub lists is $\Theta \left(n\lg \left(n/k\right)\right)$ .

Explanation of Solution

There are $n/k$ sub lists of length k and then merge the $n/k$ sorted sub lists in a list of length n .

For this, take two sublists and merge them simultaneously. The time taken by this process is $\lg \left(n/k\right)$ steps. Now, compare n elements in each step.

Hence, the worst case running time to merge the sub listsis $\Theta \left(n\lg \left(n/k\right)\right)$ .

(c)

Program Plan Intro

To find the largest value of k as a function of n so that the modified algorithm has same running time as standard merge sort.

Explanation of Solution

Merge sort is a sorting algorithm that uses divide and conquer method. In merge sort, divide the input sequence in two halves and then sort them, Finally, merge the sorted halves.

The modified algorithm has same running time as standard merge sort if $\Theta \left(n\lg \left(n/k\right)\right)=\Theta \left(n\lg n\right)$ and consider that $k=\Theta \left(\lg n\right)$ .

  $\begin{array}{l}\Theta \left(n\lg \left(n/k\right)\right)=\Theta \left(nk+n\lg n-n\lg k\right)\\ =\Theta \left(n\lg n+n\lg n-n\lg \left(\lg n\right)\right)\\ =\Theta \left(2n\lg n-n\lg \left(\lg n\right)\right)\\ =\Theta \left(n\lg n\right)\end{array}$

Hence, the running time of the modified algorithm has same as standard merge sort if $\Theta \left(n\lg \left(n/k\right)\right)=\Theta \left(n\lg n\right)$ and $k=\Theta \left(\lg n\right)$ .

(d)

Program Plan Intro

To choose the value of k in practice.

Explanation of Solution

Merge sort is a sorting algorithm that uses the divide and conquer method. In merge sort, divide the input sequence in two halves and then sort them. Finally, merge the sorted halves.

For considering the value of k, choose the largest length of sub list as kso that insertion sort becomes faster than merge sort.