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:

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

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

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

4. The unsigned integers are not sorted

5. The file can contain duplicated integers

6. 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).

7. All the buffers in memory support ±4 bytes of additional memory allocation.

8. You must use a Divide and Conquer algorithm to solve this problem

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

(b) Input and Output

1. 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,10,88,100,99,99

2. 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

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

3. Compute the complexity function, the I/O cost of operations, and the Θ(g(n)) time complex- ity of your algorithm using your pseudocode from problem (2). For the complexity function and time complexity use the substitution method and then check your result with the Master Theorem. For the I/O cost define it as a function of N. Where N is the number of blocks (4KIB) in pass 0 of this algorithm

4. Modify your algorithm from problem (1) to support files of any size (not only 2x). For in- stance in problem (1), we were assuming that the file size is in the form of 2x such as 2KIB, 4KIB, 16KB..... However, your new modification should include files of any size such as 3KIB, 37KIB.....

In addition, do you think that the time complexity of this algorithm has been optimized as a result of the modifications applied? Why?