troubleshooting Question

improved external merge sort

Avatar of kinghalls
kinghalls asked on
Algorithms
109 Comments1 Solution2017 ViewsLast Modified:
I just learned about using buffer space to improve external merge sort, I don't quite understand the algorithm though, but here it is:

Say I want to sort this:

6 4 16 11 7 5 9 2 8 12 10 3 1 13 14 15 18 17 20 19 23 21 22
we have a block each with 3  capacity and the buffer has 3 blocks

so first we should put the numbers in blocks:

6 4 16      11 7 5        9 2 8

what's next?
Given: Unordered file of records; B = # of available buffers
 
Pass 0: repeat
           Fill B buffers with blocks from file
           Sort the records in the buffers
           Output the sorted run of records
        until input file is exhausted
        // now use B-1 buffers for input and 1 for output
 
Passes 1-n
        While the number of sorted runs is > 1:
            While the input file still has unread runs:
              Repeat
                Bring in one block each from the next B-1 runs
                Merge those blocks into the output buffer (dumping as it fills)
              until the longest of those B-1 runs is exhausted
           end while
        end while
ASKER CERTIFIED SOLUTION
Join our community to see this answer!
Unlock 1 Answer and 109 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 109 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros