a$.$ Consider a parallel algorithm for sorting an array of $\text{'}\backslash ($ n $\backslash )\text{'}$ elements using comparison based sorting. The algorithm runs in $\text{'}\backslash ($ n $\backslash )\text{'}$ steps such that step $1$ has $\text{'}\backslash ($ n $\backslash )\text{'}$ instructions that can be executed in parallel and all the remaining steps have 'log n$\text{'}$ instructions. Suppose the algorithm uses $\text{'}$ n $\text{'}$ processors. Is the algorithm optimal? If not, can you make it optimal? Justify your answer.

b$.$ Consider an algorithm using a collision CRCW model and $10$ processors. Following table represents the $10$ processors, the memory location each processor will write to and the data that will be written to the respective memory locations.

Also, let the old data in memory locations $\backslash (\backslash$mathrm$\{$ml$\},\backslash$mathrm$\{$m$\}2,\backslash$mathrm$\{$~m$\}3,\backslash$mathrm$\{$~m$\}4,\backslash$mathrm$\{$~m$\}5,\backslash$mathrm$\{$~m$\}6\backslash )$ and m $7$ be $100,40,170,20,90,12$ and $38$ respectively.

Explain briefly, how the above task will be accomplished if we have $4$ processors. Show all the steps.