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?