Code Author

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

/**
 * @author

 * Code Author
 */
import java.util.*;
public class D_C_MergeSort {
   static Scanner console = new Scanner(System.in); 
   
   
   //method for sorting array elements using merge sort
   public static void mergesort(int[] a,int[] t,int l,int u)
   {
       int m ;
        if (l<u)
        {
            m = (l+u)/2;      //middle term
            mergesort(a,t,l,m); //using rcursive method 
            mergesort(a,t,m+1,u);
            merge(a,t,l,u);
        }
   }
   
   //method for merging array elements 
   public static void merge(int[] a,int[] t,int l , int u)
   {
    int m =(l+u)/2;
    int i=l,j=m+1;
    int k;
    
    for(k=l;i<=m && j<=u;k++)
    {
        if(a[i]==a[j])
        {
         t[k++]=a[i];
         t[k]=a[i];
         i++;
         j++;
        }
        else if(a[i]<a[j])
        {
            t[k]=a[i];
            i++;
        }
        else
        {
            t[k]=a[j];
            j++;
        }
    }
    
    //filling the sorted elemts
    for(;i<=m;)
         t[k++]=a[i++];
    for(;j<=u;)
        t[k++]=a[j++];
    
    //copying content to original array
    for(i =l;i<=u;i++)
        a[i]=t[i];
    
    
   }
    
   public static void main(String args[])
   {    
       
       
       //giving the aaray size to store the elements
       System.out.print("Enter the size of the array : ");
       int n = console.nextInt();
       
       //creating integer datatype array of size n
       int[] array = new int[n];
       int[] temp = new int[n]; //temporary array to store data
       
       //Filling the array
       System.out.print("Enter the contents to the array : ");
       for(int i = 0;i<=n-1;i++)
       {
         array[i]=console.nextInt();  
       }
       
       //displaying array content before sorting
       System.out.print("\n Unsorted array : ");
       for(int a:array)
         System.out.print(a + " ");
       System.out.println();
       
       //calling method mergesort to stort elements of the array
       mergesort(array,temp,0,n-1);
       
       //Displaying sorted array
       System.out.print("Sorted array is : ");
       for(int b:array)
       System.out.print(b +" ");
       System.out.println();
       
       
   }
}