$3$ VoodooSort

Here$$s a simple recursive sorting algorithm that we will call VoodooSort:

$//$ Sort array A$[]$ between indices p and r inclusive.

$//$

VoodooSort $($A$,$ p$,$ r$)\{$

$//$ Base Case: use InsertionSort

$//$

if $($r $-$ p $<12)\{$

InsertionSort$($A$,$ p$,$ r$)$ ;

return ; $//$ add return statement to base case

$\}$

$//$ Break the array into $1$st quarter, $2$nd quarter and second half

$//$

n $=$ r $-$ p $+1$ ; $//$ number of items in A$[$p$..$r$]$ inclusive

q$1=$ p $-1+$ n$/4$ ; $//$ end of $1$st quarter

q$2=$ q$1+$ n$/4$ ; $//$ end of $2$nd quarter

$//$ Sort the $3$ pieces

$//$ using VoodooSort, HeapSort and VoodooSort

$//$

VoodooSort $($A$,$ p$,$ q$1)$ ;

HeapSort $($A$,$ q$1+1,$ q$2)$ ;

VoodooSort $($A$,$ q$2+1,$ r$)$ ;

$//$ Merge the $3$ sorted arrays into $1$ sorted array

$//$

Merge $($A$,$ p$,$ q$1,$ q$2)$ ; $//$ Merge $1$st & $2$nd quarter

Merge $($A$,$ p$,$ q$2,$ r$)$ ; $//$ Merge $1$st & $2$nd halves

return ;

$\}$

In the following, you may assume without providing any proof that the worst case running times

of InsertionSort, HeapSort and Merge are $\backslash$Theta $($n

$2$

$),\backslash$Theta $($n log n$)$ and $\backslash$Theta $($n$),$ respectively.

$1.$ Write down a recurrence relation for the worst case running time of VoodooSort. Briefly

justify your answer.

$2.$ Prove the best upper bound you can on the worst case running time of VoodooSort.

$3.$ Prove the best lower bound you can on the worst case running time of VoodooSort.