## Description

In this project, you will write a program to simulate an external sorting algorithm.

External sorting is used in scenarios in which the size of the dataset to be sorted exceeds

the capacity of the main memory. In the first stage of external sorting, the dataset is

divided into a set of smaller, unordered sublists. Each sublist is then transferred from

disk to memory and sorted individually using an efficient internal sorting algorithm,

such as quicksort. Finally, the sorted sublists are efficiently merged together on disk

into a single sorted dataset.

To begin simulating external sort, you will first read an unsorted list of integers

stored in file into an n × m matrix, where n represents the number of unordered

sublists and m is the number of integers comprising each sublist. Next, you will sort

each of the n sublists individually using quicksort. To ensure that your quicksort runs

in O(mlogm) time in the worst case, you must implement a partition function with the

pivot element set as the median of the first, middle, and last elements of the sublist

given as input. In the final stage, you will merge together the n sorted sublists into a

single output list using a multiway merge that runs in O(mlogn) time. To achieve a

O(mlogn) runtime, first create a min heap from the first elements of each sorted sublist.

(Consequently, you will have a size n min heap.) Next, extract the min element from the

min heap and place it into a 1D, sorted output list. Return back to the min heap and

replace the previously extracted min element with its successor from their originating,

sorted sublist. If the min element was the largest in its sublist, move directly on

to extracting the next min element in the min heap. Repeat this process until all

sublists have been merged into the 1D, sorted output list. Rather than implementing a

min heap from scratch, you may instead use the standard heap functions in the C++

algorithm library (http://en.cppreference.com/w/cpp/algorithm) or you may use

the priority queue from the C++ queue library (http://en.cppreference.com/w/

cpp/container/priority_queue).

You have been provided a driver program that reads in the test input, makes calls

to the quicksort and multiway merge functions, and outputs the final sorted results.

Do not modify the main function and do not rewrite any of the existing function

headers. You may however implement extra helper functions or data structs if you feel

it necessary.

Input

Input is read from the keyboard. The first line of input is the number of unordered

sublists n. The second line is the number of integers m comprising each unordered

sublist. The third line is an unordered, space-delimited list of n ∗ m integers.

1

Output

Output the externally sorted list of integers using space as a delimiter.

Sample Test Case

Use input redirection to redirect commands written in a file to the standard input, e.g.

$ ./a.out < input1.dat.

Input 1

4

5

100 28 83 22 3 4 1 0 222 425 42 49 599 58 79 934 41 23 444 422

Output 1

0 1 3 4 22 23 28 41 42 49 58 79 83 100 222 422 425 444 599 934

Turn In

Submissions are through blackboard. If you have multiple files, package them into a

zip file.

Grading

Total: 100 pts.

• 10/100 – Code style, commenting, general readability.

• 05/100 – Compiles.

• 05/100 – Follows provided input and output format.

• 80/100 – Successfully implemented external sort.

2