Merge Sort

Uses divide and conquer approach → divide n elements to n sorted list with 1 element each → merge the sorted list

Merge Algorithm : MERGE(A, 9, 12, 16)

In the MERGE(A, 9, 12, 16) function, the subarray A[9:16] has the values {2, 4, 6, 7, 1, 2, 3, 5}. The function splits this subarray into two smaller arrays: L (which contains {2, 4, 6, 7}) and R (which contains {1, 2, 3, 5}).

The while loop (from lines 8–18) is responsible for merging these two arrays back into the original subarray A[9:16] in sorted order. Here's what happens step by step:

1. Tan positions in A represent values that have already been placed in their final sorted spots.
2. Tan positions in L and R represent values that are still waiting to be copied into A.
3. Blue positions in A represent places that will be filled with values from L or R.
4. Dark positions in L and R represent values that have already been copied into A.

Parts (a)–(g) show each step of the loop as it copies values from L and R back into A. By part (g), all the values from R have been copied into A, so the loop ends.

In part (h), the loop finishes, and the remaining values from L are copied back into A in sorted order by the second set of while loops on lines 20–23 and 24–27. Since all values from R were already copied, the loop on lines 24–27 doesn't run at all.

Finally, the subarray A[9:16] is now completely sorted!

The operation of merge sort on the array A with length 8 that initially contains the sequence {12, 3, 7, 9, 14, 6, 11, 2}

When we analyze how long a divide-and-conquer algorithm (like Merge Sort) takes to run, we break it into three steps: