Hello YouTube, and welcome back to sorting algorithms
In the previous episode we covered the concepts behind Merging.
In this episode we'll use the concepts learnt for the purposes of sorting, with the Merge Sort.
Now, incidentally, you'd recall that in Episode 6 we discussed the Bucket Sort. The merge sort works on a very similar concept.
Merge sort starts off simply by repeatedly breaking the unsorted list into equal halves
and continually repeating the same process for the sublists, until eventually each sublist contains at most one item.
The reason why merge sort must break each sublist down to single items is because merging doesn't work on unsorted lists
And a list of one item can be considered sorted.
Sure, the algorithm can check if a sublist ends up already sorted, but that takes up processing time, and is a little too advanced for this episode.
What do you think happens once the sublists have all been created? They are merged, of course!
Remember that merging can only create sorted lists as a result, and thus sorted sublists are the result of every merge.
What basically happens now, is that the single-item sublists are merged to form sorted sublists
and the sorted sublists are merged again to form even larger sorted sublists.
The process repeats itself until eventually the items merge back into one large, sorted list.
So how does the Merge Sort fare under the Big O Notation?
You realise that for other sorting algorithms, the amount of time required depends on the actual values of the input data
but it doesn't matter for merge sort. No matter what the values are, merge sort will split up a list into single-item sublists, then merge them all
Recall that merging too, does not depend on the values of the data items.
And yes, this means that the Merge Sort, similar to merging, has the same value for the Best, Average and Worst case time complexities under the Big O Notation
The efficient timing of O(n log n).
Here's one more point to note: Remember that in episode 7, when we discussed Quicksort
I introduced you to the term "Divide and Conquer Algorithm".
Recall that I told you that divide and conquer algorithms are extremely efficient because they reduce the amount of items they need to process by half each time.
That explains why Merge Sort breaks down lists in half each time - It's the quickest way.
That's all for this episode of sorting algorithms. Stay tuned for the next episode, the Strand sort
which is actually a variation of the merge sort. You're watching 0612 TV.
