The following is an unusual sorting algorithm. Assume that n is a power of 2 (i.e., n = 2k for some positive integer k); this will guarantee that an array can always be broken into two equal halves. What is the complexity of the algorithm for an array of length n, which begins execution from the START procedure? I will give you the following hints to nudge you in the correct direction. Remember that functions execute inward out. So, first analyze the complexity of the weirdSortHelper procedure. Once you have obtained the complexity for weirdSortHelper, proceed to weirdSort. Notice that the work outside of recursion is the weirdSortHelper call, this complexity you have already analyzed before in the previous bullet point; use it here. Use the above hints to obtain the recurrence relations for weirdSort and weirdSortHelper. Then, solve those recurrence relations (using the Master Theorem). You must state the recurrence relations; just stating the answer (even if it is correct) won't fetch full credits. Rubric: Recurrence relation for weirdSortHelper carries 9 points: 6 points for the recursive part, and 3 points for the work outside recursion. Solving the weirdSortHelper recurrence using Master Theorem carries 3 points. Recurrence relation for weirdSort carries 7 points: 4 points for the recursive part, and 3 points for the work outside recursion. Stating the final complexity using Master Theorem carries 3 points. Caution: Pay attention to weirdsortHelper. If you get that incorrect, you will get weirdSort incorrect as well. I will part mark a bit, but you will still lose the bulk of the points. Algorithm: void start(int A[], int n) { weirdSort(A, 0, n-1) } void weirdSort(int A[], int left, int right) { int mid = (left+right)/2; weirdSort(A, left, mid); weirdSort(A, mid+1, right); weirdSortHelper(A, left, right); } void weirdSortHelper(int A[], int left, int right) { if (left == right) return; else if (left + 1 == right) if (A[left] > A[right]) swap A[left] and A[right] else { int n = right - left + 1; for (int i = left; i < left + n/4; i++) swap A[i+n/2] and A[i+n/4]; int mid = (left+right)/2; weirdSortHelper(A, left, mid); weirdSortHelper(A, mid+1, right); weirdSortHelper(A, left+n/4, left + 3n/4); } }