Challenge: Implement Merge

The merge() function should merge the sorted subarrays in $array[p \cdots q]$ and $array[q+1 \cdots r]$ into a single sorted subarray in $array[p \cdots r]$. The function starts by allocating two temporary arrays, lowHalf and highHalf, and copying $array[p \cdots q]$ into lowHalf and $array[q+1 \cdots r]$ into highHalf.

You should complete the function:

• Make it repeatedly compare the lowest untaken element in lowHalf with the lowest untaken element in highHalf and copy the lower of the two back into array, starting at $array[p]$.

• Once one of lowHalf and highHalf has been fully copied back into array, the remaining elements in the other temporary array are copied back into array.

Note: Use indexes i, j, and k to access elements in lowHalf, highHalf, and array.