Interview programming challenge 5#

This post gives you answer for the question posted at

http://www.dev102.com/2008/05/26/a-programming-job-interview-challenge-5-records-sorting/

You are asked to sort a collection of records. The records are stored in a file on the disk, and the size of the file is much bigger than available memory you can work with. Assume a record size is 10 bytes and file size is 1GB. you read and write data to/from disk in units of pages where each page is 1KB big. You have few (less than 10) available pages of physical memory. Assume you are given a method to compare two records.

How can you sort the records under the described conditions?

* Hint - Using the virtual memory is not the correct answer.

The appropriate solution for this problem would be to use algorithm based on Insertion Sort