The Merge Step

Merging two sorted arrays into one takes $O(n)$.

Two pointers, one per array. Compare, take smaller, advance pointer.

Example: Merge $[3,27,38]$ and $[9,10,82]$: $1.$ $3 < 9$: take $3$ → $[3]$

$2.$ $27 > 9$: take $9$ → $[3,9]$

$3.$ $27 > 10$: take $10$ → $[3,9,10]$

$4.$ $27 < 82$: take $27$ → $[3,9,10,27]$

$5.$ $38 < 82$: take $38$ → $[3,9,10,27,38]$

$6.$ Take $82$ → $[3,9,10,27,38,82]$