SHARE
TWEET

Untitled

a guest Jul 17th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3. public class MergeSort {
  4.     public static void main(String args[] ) throws Exception {
  5.         Pair[] arr=new Pair[5];
  6.         arr[0]=new Pair(0,5);
  7.         arr[1]=new Pair(1,2);
  8.         arr[2]=new Pair(2,4);
  9.         arr[3]=new Pair(3,1);
  10.         arr[4]=new Pair(4,3);
  11.        
  12.         for(int i=0;i<5;i++){
  13.             System.out.println(arr[i]);
  14.         }
  15.        
  16.         System.out.println("--------------------------------");
  17.        
  18.         mergeSort(arr,0,4);
  19.        
  20.         for(int i=0;i<5;i++){
  21.             System.out.println(arr[i]);
  22.         }
  23.    }
  24.    
  25.    public static void mergeSort(Pair[] arr,int l,int h){
  26.        if(l<h){
  27.            int m=(l+h)/2;
  28.            mergeSort(arr,l,m);
  29.            mergeSort(arr,m+1,h);
  30.            merge(arr,l,m,h);
  31.        }
  32.    }
  33.    
  34.    public static void merge(Pair[] arr,int l,int m,int h){
  35.        
  36.        int n1=m-l+1;
  37.        int n2=h-m;
  38.        
  39.        Pair L[];
  40.        Pair R[];
  41.        L=new Pair[n1];
  42.        R=new Pair[n2];
  43.        for(int i=0;i<n1;i++){
  44.            L[i]=arr[l+i];
  45.        }
  46.        
  47.        for(int i=0;i<n2;i++){
  48.            R[i]=arr[m+1+i];
  49.        }
  50.        
  51.        int i=0,j=0,k=l;
  52.        while(i<n1 && j<n2){
  53.            
  54.            int val1=L[i].getValue();
  55.            int val2=R[j].getValue();
  56.            if(val1<=val2){
  57.                arr[k]=L[i];
  58.                i++;
  59.            }
  60.            else{
  61.                arr[k]=R[j];
  62.                j++;
  63.            }
  64.            k++;
  65.        }
  66.        
  67.        while(i<n1){
  68.            arr[k]=L[i];
  69.            i++;
  70.            k++;
  71.        }
  72.        
  73.        while(j<n2){
  74.            arr[k]=R[j];
  75.            j++;
  76.            k++;
  77.        }
  78.    }
  79. }
  80.  
  81. class Pair{
  82.    
  83.     int index;
  84.     int value;
  85.    
  86.     public Pair(int index,int value){
  87.         this.index=index;
  88.         this.value=value;
  89.     }
  90.    
  91.     public int getValue(){
  92.         return this.value;
  93.     }
  94.    
  95.     public String toString(){
  96.         return "Index="+index+" value="+value;
  97.     }
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top