Tip:
Highlight text to annotate it
X
Hello YouTube and welcome to another seemingly-random-but-actually-very-important episode of Sorting Algorithms!
In this episode, we cover the concept of merging.
That is - the combination of two sorted lists such that the combined list remains sorted.
Let's say we have two lists we want to combine.
These two lists must first be sorted, otherwise this technique won't work.
We place these lists side by side like so.
Now, we can only remove items from the left end of each list, and only the leftmost item of each list will be in consideration at any time.
The concept is this: Each time we compare two items, we'll pick out the smaller one
and use that to construct our new list.
Because we keep picking out the smallest one of the two smallest numbers in the sorted sublists
there's no chance we'll get a number too big for the combined list.
In practise, it looks somewhat like this: We compare the leftmost items of each list
and we pick the smaller of the two, and place it in our new list.
That's basically the entire process, and now that needs to repeat itself until both sublists are completely emptied.
Note that now, "2" and "3" are compared. While they might not be on the same "level"
they are the leftmost items, and that's the most important.
Now, there is something that can be said about efficieny - You realise that, since there is no sorting involved
merging can be done really quickly
Also, because of the predictability of what's going to happen in a merging
there is no distinction between the Best, Worst, and Average time complexities under the Big O Notation.
The time complexity for every merge is exactly O(n + m), n and m representing the size of each list.
The reason for this value is simply because every item in the list is processed exactly once.
That's it, actually! This episode is pretty short and really simple
but it's completely necessary because the next two episodes depend on your completely understanding this theory to work!
In the next episode of the series we take a look at the Merge Sort.
There you go, the name proves this episode's relevance!
Thanks for dropping by, you're watching 0612 TV.