A professor has proposed the following "elegant" sorting algorithm: Sort(A,i,j) { Let A be an array containing n distinct numbers, and let i,j be integers such that 1i,jn. Sort (A,i,j) sorts A[i],A[i+1],,A[j] in non-decreasing order. } begin if A[i]>A[j] then exchange A[i]A[j]; if i+1j then return; k(ji+1)/3; RRound down Sort(A,i,jk); First two-thirds are sorted Sort(A,i+k,j); \{Last two-thirds are sorted Sort(A,i,jk); First two-thirds are sorted again \} end; For a real number x,x denotes the maximum integer m satisfying mx. Answer the following questions. (1) Prove that Sort (A,1,n) correctly sorts the n elements of the input array A in non-decreasing order. (2) Give a tight asymptotic ( -notation) bound on the worst-case running time of Sort. You may ignore round-up or round-down in the evaluation