Consider how you would sort a file that was too large to fit in your machine's RAM. External Sorting refers to the sorting of data which is not in the primary memory of the computer. In this problem, you have to implement a miniature version of external sort. The file sizes have been intentionally kept small because of time constraints. The methodology followed has to be the same as for really big files.

a) First generate a 256 MB file Bigfile containing integers. You can make use of a random number generator, with suitable modifications on the generator output, to generate suitable integers.

b) Then sort the above file in the following manner

• Bring in 1024*1024 integers into memory at a time, and sort into an output file, thus generating 64 sorted files of integers.

• Do an 8 way merge on the contents of these files to generate 8 sorted files.

• Do a 4-way merge on the above files to generate 2 sorted files.

• Merge the two files obtained above into Bigfile, to obtain the sorted Bigfile.