Chapter Name: Merge Sort Please visit: gate.appliedroots.com/ For any queries you can either drop a mail to Gatecse@appliedroots.com or call us at +91 844-844-0102 Refer: en.wikipedia.org/wiki/Externa...
This is one of the best explanation on external merging. I saw so many videos but no one could explain it correctly. Thanks alot for this incredible explanation.
Everyone seems to have forgotten about this, but a replacement-selection run-distribution algorithm would produce 2x2GB files and 1x1GB sorted files; avoid the initial split step, saving 5GB of disk space; and would then only need a 3-way merge rather than a 5-way merge. This would all be considerably faster than what you have described here.
One of the best explanation related to merge sort which can be extended to K-way merge and later the external sorting, Thank a lot for the wonderful explanation
Great explanation, great handwriting even using the mouse. It's amazing , that you provided some other information about this apart from algorithm explanation.. bravo🎆
Important note that at 16:25: The sort has to be in-place (i.e. only using constant space or O(1) space) because you're sorting 1GB using 1GB RAM, so, there's no memory left to store the sorted output in the RAM.
This was so extremely helpful. I was completely lost with my teacher's explanation for this, but you speak so clearly and thoroughly. This is an amazing explanation. I have a question though, why would someone use merge and not heap to do external sorting? Isn't heap more efficient time and space wise?
18:08 There is an error in this logic. There is no guarantee that those 250Mb files will be sorted with the least items in first file, then second then third and so forth.
Can you please explain 1.why you choose 150MB from each chunk and left 250 for merge , 2. Varying these will cause computation cost, how to compute these value optimally?
this explanation is great god tier but please please can someone please send me the copde instead of watrching this video that could be a great help indeed
Thank you, great explanation. I have one question though. How do we know the second 150 MB of File_1_Sorted will not have an element smaller than an element in the first 150 MB of File_2_Sorted? In that case, we would have to compare output 2 and output 1. Imagine first 150 MB of File_1_Sorted = [1, 2, 3, 4], first 150 MB of File_2_Sorted = [9,10,11,12], second 150 MB of File_1_Sorted = [5,6,7,8]. In that case, 5,6,7,8 will be placed in the second output so not all of the elements in the first output will be smaller than output 2. I would appreciate it if someone can explain it. Best!
For external sorting, the way that the k-way merge algorithm would work is that you don't finish processing one array once it's over. Taking your example, once we have covered the first 150 MB of File_1_Sorted, we would load the next 150 MB of File_1_Sorted immediately rather than just copying the elements of File_2_Sorted into output. So now, 5 would be compared against 9 and 5 would be stored to output, 6 would be stored next and so on. We would directly copy elements of one array to output only when processing of one of the files is completely done. In the above example, when we have processed entire 1 GB data of File_1_Sorted, only then we can directly copy elements of File_2_Sorted to output. Hope this helps!
Isn't this step wrong, where you are saying that You will get sorted output by combining these files? Let me give you an example. Take arrays A1 = {1, 2, 3, 4} A2 = {10, 12, 13, 14} A3 = {20, 34, 45}. Now let's say I perform 3 way merge, taking 2 elements per array at a time. The remaining RAM can contain max of 6 elements. So O1 = {1, 2, 10, 12, 20, 34} Again I perform 3 way merge for remaining elements. O4 = {3, 4, 13, 14, 45}. Now check yourself, if concatenating these is producing the correct sorted array?
