Question

Show step by step how the merge procedure of merge sort will merge the arrays 1, 3, 4, 7, 9, 11, 13, 14 and 2, 5, 6, 8, 10, 12

Answer 1

1, 3, 4, 7, 9, 11, 13, 14 and 2, 5, 6, 8, 10, 12
There are above two lists given.
This does not change the sequence of appearance of items in the original. Now we divide these two arrays into halves.

After divinding the list in two items lists we get the below lists:
(1, 3) (4, 7) (9, 11) (13, 14) (2, 5) (6, 8) (10, 12)

We further divide these arrays and we achieve atomic value which can no more be divided.

1 3 4 7 9 11 13 14 2 5 6 8 10 12

Now, we combine them in exactly the same manner as they were broken down

We first compare the element for each list and then combine them into another list in a sorted manner. We see that 1 and 3 are in sorted positions. We compare 4 and 7 and see that they are in sorted positions.We compare 9 and 11 , they are also in sorted positions same for 13 and 14.
In the second list, we see that 2 and 5 are in sorted positions, same for pair 6 and 8 and pair 10,12

so now the list becomes:
(1, 3) (4, 7) (9, 11) (13, 14) (2, 5) (6, 8) (10, 12)

In the next iteration of the combining phase, we compare lists of two data values, and merge them into a list of found data values placing all in a sorted order.

we compare 1 and 4, and keep 1 in first position, then compare 3 with 4 and keep 3 in second position and 4 and 7 in third and fourth position. similarly we follow the iteration for other lists. and the final list beccomes
(1, 3, 4, 7) (9, 11, 13, 14) (2, 5, 6, 8) (10, 12)

In the next iteration of the combining phase, we compare lists of four data values, and merge them into a list of found data values placing all in a sorted order.

(1, 3, 4, 7, 9, 11, 13, 14) (2, 5, 6, 8, 10, 12)

After the final merging, the list should look like this

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)