Overview of External Merge Sort External merge sort is useful when the data to be sorted is too big to fit into memory.

[answerhappygod]

Overview Of External Merge Sort External Merge Sort Is Useful When The Data To Be Sorted Is Too Big To Fit Into Memory 1 (432.76 KiB) Viewed 32 times

Overview of External Merge Sort External merge sort is useful when the data to be sorted is too big to fit into memory. The basic idea is to sort the data in chunks and combine these chunks using K-way merge sort. Assume that we have N unsorted elements in a data file, and the main memory allows to keep only M data items at any given time. In the first stage of the algorithm, M items are read from the file. These M items are sorted and written to a temporary output file. Such a set of M items is called a run. In your implementation, you must use the "sort" function available in K sorted runs are merged at a time until there is a single run left (which comprises the final output). To sort K runs, a single item is read from each of the K runs and inserted into a priority queue (You must use the "priority_queue" container from the library for this purpose). The smallest item is then removed from the priority queue and saved to a temporary output file. A new data item is read from the run where the smallest item originally came from and is inserted into the queue. The process is repeated until all the items from K runs are read and saved into the temporary file in sorted order. The merge stage is repeated hierarchically in multiple passes. The example below shows a 2-pass external merge sorting for K=3. Implementation Instructions: Implement your program in Python or Java and submit your code as a single "extmerge.py" or "extmerge.java" file. You are free to use data structures and algorithms available in the programming language of your choice. Your program should not create any extra temporary files. You are not allowed to use any external libraries or packages. You are not supposed to write a project report, however you should include detailed comments in your code about how it works. You must use only two files: the original "extmerge.inp" input file and the "extmerge.out" output file. You can alternate between these two files during each pass, using one of them as input and the other one as temporary output file. Input File Format: The "extmerge.inp" file is given in the following binary format. The data to be sorted are double precision floating numbers. The number of data items N is not given in the input file; you need to deduce it from the file size. You can ignore the value for the number of passes P given in the input file. Output File Format: The "extmerge.out" output file needs to be in the same binary format as the input file. The value P needs to be the correct number of passes your program used in external merge sort. Grading Rules: All the code must be written by you. Do not copy-paste any portion of your code from other sources. Your source code will be checked automatically for plagiarism (against other students' homeworks, and against the web).