Input: data$1$: array with n integers

Input: data$2$: array with n integers

Input: n: size of data$1$ and data$2$

Output: array of size $2$n containing all elements of data$1$

and data$2$ where

output$[1]<=$ output$[2]<=...<=$ output$[2$n$]$ Algorithm: MysterySort

Sort data$1$ using SelectionSort Sort data$2$ using SelectionSort Append $\backslash$infty to data$1$ and data$2$ output $=$ Array$(2$n$)$ left$=$right$=1$ fori$=1$to$2$ndo

if data$1[$left$]<=$ data$2[$right$]$ then output$[$i$]=$ data$1[$left$]$

left $=$ left $+1$

else

output$[$i$]=$ data$2[$right$]$

right $=$ right $+1$ end

end

return output$1.$ Prove that output$[$i$]$ is less than or equal to everything in data$1[$left$..$n$]$ and data$2[$right$..$n$]$ after every iteration of the for loop in MysterySort.

$2.$ Briefly argue why output$[1]<=$ output$[2]$ after the second iteration.