In java

can anyone please tell me both a and b solutions

Segment 9.8 introduced you to an iterative merge sort. This project continues that discussion by providing more details about the merge steps. a. If n is a power of 2, as it is in Figure 9-3, you would merge pairs of individual entries, starting at the beginning of the array. Then you would return to the beginning of the array and merge pairs of twoentry subarrays. Finally, you would merge one pair of four-entry subarrays. Notice that the subarrays in each pair of subarrays contain the same number of entries. In general, n might not be a power of 2. After merging a certain number of pairs of subarrays, you might have too few entries left to make up a complete pair of subarrays. In Figure 9-13a, after merging pairs of single entries, one entry is left over. You then merge one pair of two-entry subarrays, and merge the leftover two-entry subarray with the leftover single entry. Parts b and c of Figure 9-13 show two other possibilities. Implement an iterative merge sort. Use the algorithm merge that was given in Segment 9.3. A private method that uses merge to merge the pairs of subarrays is useful. After the method completes its task, you can handle the leftovers that we just described. b. Merging two subarrays requires an additional temporary array. Although you need to use this extra space, you can save much of the time that our earlier merge algorithm spends in copying entries from the temporary array back to the original array. If a is the original array and t is the temporary array, you first merge subarrays of a into the array t. Instead of copying t back to a and continuing the merge, you determine subarrays of t and merge them into a. If you can do this an even number of times, no additional copying is necessary. Make these changes to the iterative merge sort that you wrote in Part a.

Iterative merge sort

9.8) Once we have the merge algorithm, developing the recursive merge sort is easy. Developing an iterative merge sort is not as simple. We begin by making some observations about the recursive solution. The recursive calls simply divide the array into n one-entry subarrays, as you can see in Figure 9-3. Although we do not need recursion to isolate the entries in an array, the recursion controls the merging process. To replace the recursion with iteration, we will need to control the merges. Such an algorithm will be more efficient of both time and space than the recursive algorithm, since it will eliminate the recursive calls and, therefore, the stack of activation records. But an iterative merge sort will be trickier to code without error. Basically, an iterative merge sort starts at the beginning of the array and merges pairs of individual entries to form two-entry subarrays. Then it returns to the beginning of the array and merges pairs of the two-entry subarrays to form four-entry subarrays, and so on. However, after merging all pairs of subarrays of a particular length, we might have entries left over. Merging these requires some care. Project 2 at the end of this chapter asks you to develop an iterative merge sort. You will see there that you can save much of the time necessary to copy the temporary array back to the original array during the merges.

Figure 9-3:

FIGURE 9-3 The effect of the recursive calls and the merges during a merge sort Effect of 12 16 calls to mergeSort 13 18 19 Merge steps 21 Copy to original array Numbers on the arrows in the figure indicate the order in which the recursive calls and the merges occur. Notice that the first merge occurs after four recursive calls to mergeSort and before other recursive calls to mergeSort. Thus, the recursive calls to mergeSort are interwoven with calls to merge. The actual sorting takes place during the merge steps and not during the recursive calls