Do Not Send C++ Code. Subject Design and Analysis

Suppose we have a sorting algorithm with following pseudocode:

If the sequence length is at most 4, sort it using bubble sort.

Else:

i. Divide the list into 5 pieces evenly, by scanning the entire list.

ii. (recursively) sort the first 3/5 of the list. iii. (recursively) sort the last 3/5 of the list. iv. (recursively) sort the first 3/5 of the list.

For example, on the input sequence 1, 5, 3, 2, 4 The first recursive sort produces 1, 3, 5, 2, 4, the second sort produces 1, 3, 2, 4, 5, and the last produces 1, 2, 3, 4, 5.

(a) Write down a runtime recurrence for this sorting algorithm and analyze its asymptotic running time.

(b) Give an example sequence on 5 or 10 integers where this sorting algorithm does not terminate with the correct answer.