Question

. Write a class with an int array as its only instance variable. Write a recursive method that uses the following recursive strategy in order to sort the array:

• ❑ Sort the left half of the array (this is a recursive call).

• ❑ Sort the right half of the array (this is another recursive call).

• ❑ Merge the two sorted halves of the array so that the array is sorted (there is no recursive call here).

Answer 1

package sort;
/*worst case of merge sort is NlogN
*    Merge sort
* {20, 13, 4, 34, 5, 15, 90, 100, 75, 102}
* / \   
* {20, 13, 4, 34, 5} {15, 90, 100, 75, 102}
* / \ / \
* {20, 13, 4}{34, 5} {15, 90, 100,} {75, 102}
* / \ / \ / \ / \
*{20, 13} {4} {34} {5} {15, 90} {100} {75} {102}
* / \ / \
*{20} {13} {15} {90}
*
*Height of above tree is Log(N)
*to merge the array two temp array it will take o(N) in worst case
*so total time complexity it O(Nlog(N))
*
*/

public class MergeSort {

   int ar[];
   MergeSort(int ar[]){
       this.ar=ar;
   }
   public void mergeSort(int ar[],int l,int r){
       if(l<r){
           int mid=(l+r)/2; //take mid index
           mergeSort(ar,l,mid); //call mergesort on first half
           mergeSort(ar,mid+1,r); // and second half
           marge(ar,l,r,mid); //no merge the two in sorted manner
       }
   }
   public void marge(int ar[],int l,int r,int mid){
       int t1[]=new int[mid-l+1]; //make temp array of first hlaf size and
       int t2[]=new int[r-mid]; //second half size
       int k=0; //index to 0
       for(int i=l;i<=mid;i++){ //copy fist half elements to first temp array
           t1[k++]=ar[i];
       }
       k=0;
       for(int i=mid+1;i<=r;i++){ //copy second half array to sec temp array
           t2[k++]=ar[i];
       }
       k=0;
       int k1=0; //from those two temp array copy elements in sorted array in original array
       while(k<t1.length && k1<t2.length){
           if(t1[k]<=t2[k1]){ //if t1's element is less first copy it
               ar[l++]=t1[k++];  
           }
           else{
               ar[l++]=t2[k1++]; //else t2's
           }
       }
       while(k<t1.length){ //copy the remaining elements
           ar[l++]=t1[k++];
       }
       while(k1<t2.length){
           ar[l++]=t2[k1++];
       }
   }
   //driver program to test
   public static void main(String[] args) {
       int A[]={20, 13, 4, 34, 5, 15, 90, 100, 75, 102};
       MergeSort m=new MergeSort(A);
       m.mergeSort(A,0,A.length-1);
       for(int i=0;i<A.length;i++){
           System.out.print(A[i]+" ");  
           }
      
   }

}

output

4 5 13 15 20 34 75 90 100 102