Question

1)

can any one please givem the code for this

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.

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

Sol: a)

this is te code i have but am getting lot of eerrors can anyone edit this plesasee?

public class MergeSortA
{
public static<T> <T extends Comparable super T>> void
mergeSortA(T[]a, int n)
{
T[]tempArray=(T[])new comparable[a.lenghth];
Int startingLeftovers=n;
For(int segmetLength =1;segmentLenght &lt;=n/2;
segmentLength =2*segementLength
{

startingeftovers=segmentPairs(a,tempArray,n,segmentLength);
int endingSegment=startingLeftovers+segmentLength-1;
if(endingSegment<n-1)
merge(a,tempArray,startingLeftovers,endingSegment,n-1);
}
if(startingLeftovers<n)
merge(a,tempArray,0,startingLeftovers-1,n-1);
}
private static<T extends Comparable super T>>int
segmentPairs(T[]a,T[]tempArray,int n,int segmentlength)
{
int mergedpairLength=2*segmentLength;
int numberOfpairs=n/mergedPairLength;
int starting Segment1=0;
for(int count =1; count<=numberOfPairs;count++)
{
int endingSegment1=startingSegment1+segmentLength-1;
int startingSegment2=endingSegment1+1;
int ending Segment2=startingSegment2+segmentLength-1;
merge(a,tempArray,startingSegment1,endingSegment1,endingSegment2);
startingSegment1=endingSegment2+1;
}
return starting Segment1;
}

private static<T extends Comparable super T>> void
merge(T[]a, T[]tempArray, int first, int mid,int last,)
{
int startingHalf1=first;
int endHalf1=mid;
int startinghalf2=mid+1;
int endHalf2=last;
int index=startingHalf1;
for(;(startingHalf1<=endHalf1)&&(startinghalf2<=endHalf2);index++)

{

if(a[startingHalf1].compare To(a[startinghalf2])<0))
{
tempArray[index]=a[startinghalf1];
startingHalf1++;
}
else
{
tempArray[index]=a[startinghalf2];
startingHalf2++;
}
}

for(;startingHalf1<=endHalf1;startingHalf1++,index++)

tempArray[index]=a[startinghalf1];

for(;startingHalf2<=endHalf2;startingHalf2++,index++)
tempArray[index]=a[startinghalf2];

for(index-first;index<=last;index++){
}
public static void main(String[] args)
{
Integer[]a={50,45,20,40,10,15,5,25,30,35,55};
System.out.println("The array before sorting is ");
for(int i = 0; i<a.length;i++)
System.out.print(a[i]+"");
System.out.print(false);
mergeSortA(a,a.length);
System.out.println("\n The array after sorting is ");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+"");
System.out.print(false);
}
}

Answer 1

//Please see the source code below I have done modification in your code to make it working please do thumbs up // if you like the solution:

public class MergeSortA
{
   public static <T extends Comparable<? super T>>
    void mergeSortA(T[] a, int n)
   {
       T[] tempArray = (T[])new Comparable<?>[a.length];
       mergeSort(a, tempArray, 0, n-1);
          
   }    
      
   private static <T extends Comparable<? super T>>
    void mergeSort(T[] a, T[] tempArray, int startIndex, int lastIndex)
   {
       if (startIndex < lastIndex)
       {
           int mid = (startIndex + lastIndex)/2;        // find the mid point in array
           mergeSort(a, tempArray, startIndex, mid);    // sorting left half array[startIndex..mid]
           mergeSort(a, tempArray, mid + 1, lastIndex); // sorting right half array[mid+1..lastIndex]

           if (a[mid].compareTo(a[mid + 1]) > 0)    
               merge(a, tempArray, startIndex, mid, lastIndex); // merge the two arrays left and right
          
       }
    }

   private static <T extends Comparable<? super T>>
   void merge(T[] a, T[] tempArray, int first, int mid, int last)
   {
       // Two arrays left and right are a[startingHalf1....endHalf1] and a[startinghalf2....endHalf2].
       int startingHalf1 = first;
       int endHalf1 = mid;
       int startinghalf2 = mid + 1;
       int endHalf2 = last;
          
       int index = startingHalf1;
                                          
       for (; (startingHalf1 <= endHalf1) && (startinghalf2 <= endHalf2); index++)
       {
  
           if (a[startingHalf1].compareTo(a[startinghalf2]) < 0)
           {
               tempArray[index] = a[startingHalf1];
                  startingHalf1++;
           }
           else
           {
                  tempArray[index] = a[startinghalf2];
                  startinghalf2++;
           }
       }
  
       for (; startingHalf1 <= endHalf1; startingHalf1++, index++)
              tempArray[index] = a[startingHalf1];
  
       for (; startinghalf2 <= endHalf2; startinghalf2++, index++)
           tempArray[index] = a[startinghalf2];
      
       // Finally copying the result to original array
       for (index = first; index <= last; index++)
           a[index] = tempArray[index];
   }
  
public static void main(String[] args)
{
   Integer[]a={50,45,20,40,10,15,5,25,30,35,55};
   System.out.println("The array before sorting is ");
   for(int i = 0; i<a.length;i++)
       System.out.print(a[i]+" ");
  
   mergeSortA(a,a.length);
   System.out.println("\nThe array after sorting is ");
   for(int i=0;i<a.length;i++)
       System.out.print(a[i]+" ");
  
}
}

OUTPUT:

The array before sorting is
50 45 20 40 10 15 5 25 30 35 55
The array after sorting is
5 10 15 20 25 30 35 40 45 50 55