merge sort merge phase

Question

I'm watching a video, demonstrating merge sort, https://www.youtube.com/watch?v=EeQ8pwjQxTM

At 5:42, happens something I do not understand.

We are merging last 2 big arrays, [4,15,50,108] and [8,16,23,42]. My understanding is - we pick each pair, since they are already in sorted arrays, and swap them if one is larger than the other. So it goes well, until 23 is smaller than 50, and next element is 42 which is smaller than 108 and we end up with [4,8,15,16,23,50,42,108].

Obviously, my understanding is faulty. But I heard no indication we go we compare each element in first array with all the elements of second one. Did I miss it? If so, how's the n log n complexity achieved, since we do n^2 operations?

Answer 1

How does the merging work?

Imagine two pointers, starting at the first element of each array. In this example I will use the #-Symbol to indicate the pointers.

This is your start configuration:

[#4,15,50,108]

[#8,16,23,42]

[ ]

Now you always compare the elements, that the pointers are pointing at and move the smaller element to the merged list. Then you move the "winning" pointer to the next element. The "loser" pointer does not move. If a pointer reaches the end of the list, the other pointer always wins.

This is your result after the first comparison:

[4,#15,50,108]

[#8,16,23,42]

[4]

4 won the comparison and therefore is added to the merged list. The pointer is moved to the next position. Now we start over and compare 15 and 8 resulting in this configuration:

[4,#15,50,108]

[8,#16,23,42]

[4, 8]

This process continues until each element is in the merged list.

After comparing 15 and 16:

[4,15,#50,108]

[8,#16,23,42]

[4, 8, 15]

After comparing 50 and 16:

[4,15,#50,108]

[8,16,#23,42]

[4, 8, 15, 16]

After comparing 23 and 50:

[4,15,#50,108]

[8,16,23,#42]

[4, 8, 15, 16, 23]

And so on...

In code these pointers could be realised by using indexes for the lists (increasing them when the pointer has to move) or using queues (always taking the first element).

How is it $O(n*log(n))$ if we do $O(n^2)$ Operations?

Because we dont. During the merge process, every element is still only visited once (you never decrease a pointer). If your merge algorithm has two lists of length $n$ for arguments, then it needs $O(2*n)$-Time but $O(2*n) = O(n)$. And with merging in $O(n)$, merge sort is in $O(n * log(n))$.

Answer 2

We do not compare elements in both the arrays one to one. We only keep smaller element and recompare the larger element. For example

4 ? 8

4 is smaller 8 is larger so we keep 4 and our two arrays are now [15, 50, 108] and [8, 16, 23, 42].

15 ? 8

8 is smaller 15 is larger so we keep [4, 8] and our two arrays are now [15, 50, 108] and [16, 23, 42].

After this we compare and keep the elements as below

Compare 15 ? 16, keep [4, 8, 15]
Compare 50 ? 16, keep [4, 8, 15, 16]
Compare 50 ? 23, keep [4, 8, 15, 16, 23]
Compare 50 ? 42, keep [4, 8, 15, 16, 23, 42]
Second array is empty so keep [50 108] in th end.
Thus we have [4, 8, 15, 16, 23, 42, 50, 108] as merged array.

For analysis head over to the solution of Recurrence Relationship for Divide and Conquer or you can learn about Master Theorem, which is more general. $T(n) = 2T(n/2) + O(n)$ is solved in Case 2 of the wiki article.