Consider the following two$-$dimensional sorting problem: we are given an arbitrary array of n$2$numbers $($unsorted$),$ and have to output an n $\backslash$times n matrix of the inputs in which all rows andcolumns are sorted.As an example, suppose n $=3$ so n$2=9.$ Suppose the $9$ numbers are just the integers$\{1,2,...,9\}.$ Then possible outputs include $($but are not limited to$)147135126258246348369789579$It is obvious that we can solve this in O$($n$2$ log n$)$ time by sorting the numbers and then usingthe first n as the first row, the next n as the second row, etc. For this question, you should provethat this is tight. Formally, you should prove that in the comparison model, this problem cannotbe solved in o$($n$2$ log n$)$ time. For simplicity, you can $($as always$)$ assume that n is a power of $2.$Hints: instead of reasoning directly about the decision tree, show that if we could solve thisproblem with o$($n$2$ log n$)$ comparisons then we could break the sorting lower bound $($we could sortan array of size n using fewer than log$($n$!)$ comparisons$).$ Useful facts to keep in mind are thatn! $>($n$/$e$)$n and that we can merge two sorted arrays of length n using $2$n $1$ comparisons. Youmight need to be careful with constants$\mathrm{.}1$