[Introduction to Algorithms, CLRS] Exercises 2.3-6

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-6

Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1 . . j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(n lg n)?

Answer:

Even though we can use a binary search to reduce the time to search the next smallest one, we cannot reduce the time to move the elements to next position to make the next smallest one be in the right position. Therefore, the overall worst-case running time of insertion sort is still Θ(n^2).

Cf.) insertion sort in Section 2.1.

INSERTION-SORT (A)

1    for j = 2 to A.length

2        key = A[j]

3        // Insert A[j] into the sorted sequence A[1..j-1]

4    i = j - 1

5    while i > 0 and A[i] > key

6        A[i+1] = A[i]

7        i = i + 1

8    A[i+1] = key

source: https://atekihcan.github.io/CLRS/E02.03-06/