Sorting phase
In the sorting phase, you start with the unitary arrays. During each step, you apply multiple merges and the overall cost is N=8 operations:
- In the first step you have 4 merges that cost 2 operations each
- In the second step you have 2 merges that cost 4 operations each
- In the third step you have 1 merge that costs 8 operations
Since there are log(N) steps, the overall costs N * log(N) operations.