Merging (2)
To merge a1[l1…r1] and a2[l2…r2] into a3[l3…r3] (where both a1 and a2 are sorted):
1. Set i = l1, set j = l2, and set k = l3.2. While i ? r1 and j ? r2, repeat: 2.1. If a1[i] is less than or equal to a2[j]: 2.1.1. Copy a1[i] into a3[k], then increment i and k. 2.2. If a1[i] is greater than or equal to a2[j]: 2.2.1. Copy a2[j] into a3[k], then increment j and k.3. If i ? r1, copy a1[i…r1] into a3[k…r3].4. If j ? r2, copy a2[j…r2] into a3[k…r3].5. Terminate.