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?
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