Sort (in ascending order) the items in a file of size 2x KIB using limited memory. Note that x is a unsigned integer where x > 0. (a) Rules:

i. The file is located in disk (not in memory)

ii. Memory is limited to 2 input buffers and 1 output buffer (4KIB each) Total memory capacity 12 KIB

iii. Assume that the contents of the file are unsigned integers separated by a comma delimiter. (i. e 3,1,3,100,99...)

iv. The unsigned integers are not sorted

v. The file can contain duplicated integers

vi. When in a file, a digit from an integer is 1 byte (datatype is char). When in a buffer, an integer is 4 bytes (data type is integer).

vii. All the buffers in memory support ±4 bytes of additional memory allocation. viii. You must use a Divide and Conquer algorithm to solve this problem

ix. Temporary files, in disk, can only hold a max size of ((#pass + 1) ∗ 4)KIB

(b) Input and Output

i. Input: a file containing unsorted unsigned integers in the range of 0 and 100 (both inclusive). For example: 100,67,99,99,1,1,3,24,88,96,37,10,1 0,88,100,99,99

ii. Output: A file containing the sorted integers from the input file. For example:

1,1,3,10,10,24,37,67,88,88,96,99, 99,99,99,100,100

Your work starts here

1. Describe the algorithm to solve the problem for a given file of size 25 first, and then describe the algorithm for a given file of size 2x (any given x). Note that x is a unsigned integer where x > 0. You can use tables, diagrams, paragraph description to describe the algorithm. Be as clear as possible, and define clearly each step taken during the process. Credit for this problem will be only given to those students that clearly define a step by step approach to solve this problem.

2. Write the pseudocode that represents your algorithm from problem (1). Note that in this problem, I am asking for the compiled LaTeX pseudocode (PDF format) instead of the LaTeX code that creates this pseudocode