I'm trying to understand how external sorting works from the book "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

The author illustrates an example where he tries to sort 81,94,11,96,12,35,17,99,28,58,41 with a memory which can hold upto M=3 numbers. He uses two input tapes Ta1,Ta2 and two output tapes Tb1,Tb2.

Ta1    81,94,11,96,12,35,17,99,28,58,41

In the first step M numbers are read into memory then, sorted and written to Tb1 and Tb2 alternatively.

Tb1    11,81,94   17,28,99   15
Tb2    12,35,96   41,58,75

I understand how the algorithm works but, don't understand why it is important to write results alternatively. Couldn't this be achieved without alternating?

  • 1
    $\begingroup$ I understand how the algorithm works please enlighten me how it arrives at 75 and 15. $\endgroup$ – greybeard Feb 21 '17 at 6:27

I believe the alternation is done to ensure that the data is split as closely as possible into equal-sized subsets, which minimizes the time spent on each later pass.

| cite | improve this answer | |
  • $\begingroup$ Needing neither upfront knowledge about the number of items/runs nor considerable memory. $\endgroup$ – greybeard Feb 16 '18 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.