Consider the following function:

function recsort$($A$,$i$,$j$)$: if A$[$i$]>$A$[$j$]$: A$[$i$],$A$[$j$]=$ A$[$j$],$A$[$i$]$ if i$+1<$j: k$=$int$(($j$-$i$+1)/3)$ recsort$($A$,$i$,$j$-$k$)$ recsort$($A$,$i$+$k$,$j$)$ recsort$($A$,$i$,$j$-$k$)$

Which of the following is true for the function recsort? $($You may assume A is nonempty$)$

Question $1$Answer

a$.$

This function always sorts the input array A in n$*$log$($n$)$ time regardless of the content of A

b$.$

The worst case runtime for this function is n$2$where n is the size of A

c$.$

The worst case runtime for this function is n$3$where n is the size of A

d$.$

None of the above