Segment 9.8 introduced you to an iterative merge sort. This project continues th
ID: 3859244 • Letter: S
Question
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:
Explanation / Answer
The required code for the mergeSort using the recursive calls is as follows. As, you have not specified the language in which you are requiring the code. So, I selected C as the language to code with. As it is the best and faster one to do these things with. Hope it will help.
sortMerge.c
#include <stdio.h>
void sortMerge(int [], int, int, int);
void parts(int [],int, int);
int main()
{
int lst[50];
int uu, sz;
printf("Enter total number of elements:");
scanf("%d", &sz);
printf("Enter the elements: ");
for(uu = 0; uu < sz; uu++)
{
scanf("%d", &lst[uu]);
}
parts(lst, 0, sz - 1);
printf("After merge sort: ");
for(uu = 0;uu < sz; uu++)
{
printf("%d ",lst[uu]);
}
return 0;
}
void parts(int lst[],int lower,int hi)
{
int middle;
if(lower < hi)
{
middle = (lower + hi) / 2;
parts(lst, lower
, middle);
parts(lst, middle + 1, hi);
sortMerge(lst, lower, middle, hi);
}
}
void sortMerge(int lst[],int lower,int middle,int hi)
{
int uu, io, qu, lo, temporary[50];
lo = lo;
uu = lo;
io = middle + 1;
while ((lo <= middle) && (io <= hi))
{
if (lst[lo] <= lst[io])
{
temporary[uu] = lst[lo];
lo++;
}
else
{
temporary[uu] = lst[io];
io++;
}
uu++;
}
if (lo > middle)
{
for (qu = io; qu <= hi; qu++)
{
temporary[uu] = lst[qu];
uu++;
}
}
else
{
for (qu = lo; qu <= middle; qu++)
{
temporary[uu] = lst[qu];
uu++;
}
}
for (qu = lo; qu <= hi; qu++)
{
lst[qu] = temporary[qu];
}
}
Please rate the answer if it helped.....Thankyou
Hope it helps.....