Chapter 2 1-2 Problems, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2-1 Insertion sort on small arrays in merge sort 
Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

1. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk) worst-case time.
2. Show that the sublists can be merged in Θ(nlg(n/k)) worst-case time.
3. Given that the modified algorithm runs in Θ(nk+nlg(n/k)) worst-case time, what is the largest asymptotic (Θ-notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort , in terms of Θ-notation?
4. How should k be chosen in practice?

Solution:
1. Sorting Sublists
 For input of size k, insertion sort runs on Θ(k²) worst-case time, i.e. running time of the form (ak²+bk+c). So, worst-case time required to sort n/k sublists, each of length k, with insertion sort:

$$T(k) = \frac n k (ak^2 +bk +c) = ank + bn + \frac {cn} k$$

 Now, k is an integer significantly smaller than n. So, for sufficiently large values of n, we can ignore the last two term of T(k). So, T(k)=Θ(nk).
 2. Merging Sublists
We have n elements divided into n/k sorted sublists each of length k. To merge these n/k sorted sublists to get a single sorted list of length n, we have to take 2 sublists at a time and continue to merge them. This will result in log(n/k) steps. And in every step, we are essentially going to compare n elements. So the whole process will run at Θ(nlg(n/k)).
3. Largest Value of k
 For the modified algorithm to have the same asymptotic running time as standard merge sort, Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk) must be same as Θ(nlgn)

To satisfy this condition, k cannot grow faster than lgn asymptotically (if k grows faster than lgn, because of the nk term, the algorithm will run at worse asymptotic time than Θ(nlgn). But just this argument is not enough as we have to check for k=Θ(lgn), the requirement holds or not.

If we assume, k=Θ(lgn),

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)

=Θ(nlgn+nlgn−nlg(lgn))

=Θ(2nlgn−nlg(lgn))

=Θ(nlgn) 

4. Practical Value of k

In practice, k should be the largest list length on which insertion sort is faster than merge sort.

2-2 Correctness of bubble-sort

Bubble-sort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. 

BUBBLESORT(A)
  for i to A.length - 1
      for j = A.length downto i + 1
          if A[j] < A[j - 1]
              exchange A[j] with A[j - 1]

1. Let A′ denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that  A′[1]≤A′[2]≤⋯≤A′[n](2.3) where n=length[A]. What else must be proved to show that BUBBLESORT actually sorts? 
2. State precisely a loop invariant for the for loop in lines 2–4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.
3. Using the termination condition of the loop invariant proved in part (2), state a loop invariant for the for loop in lines 1–4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter. 
4. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

Solution:
1. Required Proof of Correctnesses
We also need to prove that A′ consists of the elements originally in A but in sorted order.
2. Loop Invariant for Inner Loop
The loop invariant for the for loop in lines 2–4 can be stated as follows:
At the start of each iteration of the for loop, the subarray A[j..n] consists of the elements originally in A[j..n] before entering the loop but possibly in a different order and the first element is the smallest among them.
And here is how the three necessary properties hold for the loop invariant:

Initialization: Initially the subarray contains only the last element A[n] and this is the smallest element of the subarray.

Maintenance: In every step we compare A[j] with A[j−1] and make A[j−1] the smallest among them. So, after the iteration, , the length of the subarray increases by one and the first element is the smallest of the subarray. 

Termination: The loop terminates when j=i+1. At that point also the length of the subarray increases by one and the first element is the smallest of the subarray as we swap A[i+1] with A[i].

3. Loop Invariant for the Outer Loop

The loop invariant for the for loop in lines 1–4 can be stated as follows:

At the start of each iteration of the for loop, the subarray A[1..i−1] consists of the elements that are smaller than the elements in the subarray A[i..n] in sorted order.

And here is how the three necessary properties hold for the loop invariant:

Initialization: Initially the subarray A[1..i−1] is empty and trivially this is the smallest element of the subarray.

Maintenance: From part (2), after the execution of the inner loop, A[i] will be the smallest element of the subarray A[i..n]. And in the beginning of the outer loop, A[1..i−1] consists of elements that are smaller than the elements of A[i..n], in sorted order. So, after the execution of the outer loop, subarray A[1..i] will consists of elements that are smaller than the elements of A[i+1..n] , in sorted order.

Termination: The loop terminates when i=A.length. At that point the array A[1..n] will consists of all elements in sorted order.

4. Running Time of Bubblesort

• At worst-case, bubblesort will iterate over the whole array for each element, i.e. for each element bubble sort will perform n comparisons and swaps. Therefore, worst-case running time of bubblesort is Θ(n²).
• Although insertion also runs at Θ(n²) worst-case time, the number of assignments (swaps) performed in bubblesort is way more than that of insertion sort. So, the constant factors in the running time will be much larger for bubblesort compared to that of insertion sort. This means, for the same input size, insertion sort will run faster than bubblesort.