Recursive Function is a function that could solve the given problem by repeatedly calling the function.
To have a functional Recursive Function, it must meet the following conditions:
Two-way Merge splits the file contents into parts where their size, \(M\), could be held by the main memory. Those parts will be sorted using one of the 202203102004 and we will pair those parts into runs which will be stored into two separate drives or tapes. We will merge two parts by comparing them sequentially until we have hit the end of the run. Follow the recursive rule, we will repeat the steps stated before until we have obtained a sorted result.
First, we will build a heap by using the first \(M\) items in the input tape or drive. After that, we will write the smallest item in the heap to the output tape or drive where later it will be deleted from the heap, and then compare it to the current first item in the input tape or drive to determine whether it is larger than the latest inserted item. If it is indeed larger, it will be added into the heap. Otherwise, it will go to the array. The steps will be done recursively until either it hit the end of the tape or the array becomes full.
Quicksort is a recursive sorting algorithm which use a pivot and compare it to other items in the array. It will split items into two sections where one represent items that are smaller than the pivot and the other larger.
Since the split is uneven, there will always be a split that finished earlier than the other. We will merge the smallest Fibonacci number in the previous pass of runs into the empty drive or tape, and split the remaining runs into the other drive or tape that does not obtain that number. Apply the recursive assumption, we will then run the progress all over again until we merge all the runs.
Mergesort is a divide by conquer sorting algorithm which emphasise on merging. It is done by divide the input array into the smallest possible arrays, sort the items inside them, and then merge the sorted arrays into an external array recursively.
Unlike 202203102127, it could use more than two, \(k\), drives or tapes as input or output. \(k\) parts will then be grouped into a run which will be stored into \(k\) drives or tapes. It is ill-advised to use comparison to obtain the smallest element among the parts since it could result in \(O(N^2)\) which is bad. We could take advantage of some #data-structure peculiarly 202202062259 or 202112102110. We will then obtain a sorted run by repeating the process recursively. The same steps will be performed for the next run.