sorting - How external merge sort algorithm works?

Question

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?

Answer 1

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