Menu
I'm trying to understand how external merge sort algorithm works (I saw some answers for same question, but didn't find what I need). I'm reading the book "Analysis Of Algorithms" by Jeffrey McConnell and I'm trying to implement the algorithm described there.
For example, I have input data: 3,5,1,2,4,6,9,8,7, and I can load only 4 numbers into memory.
My first step is read the input file in 4-number chunks, sort them in memory and write one to file A and next to file B.
I got:
A:[1,2,3,5][7] B:[4,6,8,9] Now my question how can I merge chunks from these files to the bigger ones if they will not fit to the memory? Jeffrey McConnell wrote that I need to read half chunks and merge them to next files C and D.
But I got wrong sequence:
C:[1,2,4,6,3,8,5,9] D:[7] Can anyone provide an example with step by step instruction, please?
PS: I understand how to merge number by number by reading from file, but how do I do it with in-memory buffers to reduce I/O operations?
249
External merge sort. One example of external sorting is the external merge sort algorithm, which is a K-way merge algorithm. It sorts chunks that each fit in RAM, then merges the sorted chunks together. The algorithm first sorts M items at a time and puts the sorted lists back into external memory.
The sorting of relations which do not fit in the memory because their size is larger than the memory size. Such type of sorting is known as External Sorting. As a result, the external-sort merge is the most suitable method used for external sorting.
Algorithm for Merge Sort Step 1: Find the middle index of the array. Step 2: Divide the array from the middle. Step 4: Call merge sort for the second half of the array. Step 5: Merge the two sorted halves into a single sorted array.
What Is a Merge Sort Algorithm? Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list.
I guess after such a long time you must have got an answer. But I am still providing some example links to help someone else who hits this question.
NOTE: Before looking into this link you should have an idea about Heap data structure Take a look at Example of Two-Way Sorting and Example of multiway external sorting and you will get a complete idea of the implementation of a external sorting algorithm
59
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
