Merge takes an input array, A $=[$a$1,...,$ an$]$ of integers such that A$[1$ : $($n$/2)]$

and A$[($n$/2)+1$ : n$]$ are both sorted and it outputs sorted version of the entire array, A$.$

Give a pseudocode for the merge procedure that runs in O$($n$)$ time.

Then, argue correctness of your pseudocode using loop invariant method. Clearly define the loop invariant and show first why the loop invariant allows you to conclude the correctness. Then show both initialization and

maintenance holds.