Scribd
Upload
143 views2 pages

Balanced Merge

A file consisting of 6,000 records needs to be sorted into a computer memory that has a capacity of 600 records. The 2-Way Balanced Merge algorithm is used. It involves: 1) Distributing the sorted runs into 2 files during an internal sorting phase, 2) Merging the files in multiple passes until all records are merged into a single sorted file.

Uploaded by

rafhuouka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
143 views2 pages

Balanced Merge

A file consisting of 6,000 records needs to be sorted into a computer memory that has a capacity of 600 records. The 2-Way Balanced Merge algorithm is used. It involves: 1) Distributing the sorted runs into 2 files during an internal sorting phase, 2) Merging the files in multiple passes until all records are merged into a single sorted file.

Uploaded by

rafhuouka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Sebuah file yang terdiri dari 6000 records, hendak disortir ke dalam memori computer yang

kapasitasnya 600 record.

2 Way Balanced Merge

10 sorted
Internal sort
6000 Subfiles
records
phase
@ 600
records
2 – way balanced merge: Assume 4 file

1) Distribute sorted runs onto 2files (may be done in conjuction with internal short phase)

2) Merge pass 1:
3
records records records records records records 1 – 1200; (Run 1)
1
4801 – 5400; 3601 – 4200; 2401 – 3000; 1201 – 1800; 1 – 600; records 2401 – 3600; (Run 3)
Merge Pass records 4801 – 6000; (Run 5)
records records records records records 1
2
5401 – 6000; 4201 – 4800; 3001 – 3600; 1801 – 2400; 601 – 1200;
4
records 1201 – 2400; (Run 2)
records 3601 – 4800; (Run 4)

3) Merge pass 2:

Run 5; Run 3; Run 1 3 1 Run 1 + 2 ;


Merge Pass Run 5.
Run 4; Run 2 4 2

2 Run 3 + 4 ;

4) Merge pass 3:

Run 1 + 2 1
Merge Pass 3 Run 1 + 2 + 3 + 4;
Run 3 + 4 2 3
5) Merge pass 4:

Run 5 1
Merge Pass 3 Run 1 + 2 + 3 + 4 + 5
Run 1 + 2 + 3 + 4 3 4 = Sorted file

You might also like