Question

the sort below shows an algorithm for sorting

aSort(A, i, j) // where A is the array to be sorted; i is the start index and j is the end index.
n = j – i + 1
If (n < 18) {
sort A[i…j] by insertion-sort
return
}
m1 = i + 2 * n / 3
m2 = i + n / 3
aSort(A, i, m1)
aSort(A, m2, j)
aSort(A, i, m1)

questions:
1) Please state the asymptotic worst-case running time for aSort with valid workings.
2) Please prove that aSort(A, 1, n) sorts the array A of n elements correctly.

Answer 1

1.The complexity function is:

T(n) = 3T(2n/3) + CONST
This is because:

You have three recursive calls for a problem of size 2n/3
The constant modifier here is O(1), since all non recursive calls operations are bounded to a constant size (Specifically, insertion sort for n<=18 is O(1)).
If you go on and calculate it, you'll get worse than O(n^2) complexity

2.

• By induction. Assume your algorithm works for problems of size n, and let's examine a problem of size n+1. For n+1<18 it is trivial, so we ignore this case.

• After first recursive call, you are guaranteed that first 2/3 of the array is sorted, and in particular you are guaranteed that the first n/3 of the elements are the smallest ones in this part. This means, they cannot be in the last n/3 of the array, because there are at least n/2 elements bigger than them. This means, the n/3 biggest elements are somewhere between m2 and j.

• After second recursive call, since it is guaranteed to be invoked on the n/3 biggest elements, it will place these elements at the end of the array. This means the part between m1 and j is now sorted properly. This also means, 2n/3 smallest elements are somewhere in between i and m1.

• Third recursive call sorts the 2n/3 elements properly, and the n/3 biggest elements are already in place, so the array is now sorted