import java.io.*;
import java.util.*;
public class MergeSort {
    public static void main(String args[] ) throws Exception {
        Pair[] arr=new Pair[5];
        arr[0]=new Pair(0,5);
        arr[1]=new Pair(1,2);
        arr[2]=new Pair(2,4);
        arr[3]=new Pair(3,1);
        arr[4]=new Pair(4,3);

        for(int i=0;i<5;i++){
            System.out.println(arr[i]);
        }

        System.out.println("--------------------------------");

        mergeSort(arr,0,4);

        for(int i=0;i<5;i++){
            System.out.println(arr[i]);
        }
   }

   public static void mergeSort(Pair[] arr,int l,int h){
       if(l<h){
           int m=(l+h)/2;
           mergeSort(arr,l,m);
           mergeSort(arr,m+1,h);
           merge(arr,l,m,h);
       }
   }

   public static void merge(Pair[] arr,int l,int m,int h){

       int n1=m-l+1;
       int n2=h-m;

       Pair L[];
       Pair R[];
       L=new Pair[n1];
       R=new Pair[n2];
       for(int i=0;i<n1;i++){
           L[i]=arr[l+i];
       }

       for(int i=0;i<n2;i++){
           R[i]=arr[m+1+i];
       }

       int i=0,j=0,k=l;
       while(i<n1 && j<n2){

           int val1=L[i].getValue();
           int val2=R[j].getValue();
           if(val1<=val2){
               arr[k]=L[i];
               i++;
           }
           else{
               arr[k]=R[j];
               j++;
           }
           k++;
       }

       while(i<n1){
           arr[k]=L[i];
           i++;
           k++;
       }

       while(j<n2){
           arr[k]=R[j];
           j++;
           k++;
       }
   }
}

class Pair{

    int index;
    int value;

    public Pair(int index,int value){
        this.index=index;
        this.value=value;
    }

    public int getValue(){
        return this.value;
    }

    public String toString(){
        return "Index="+index+" value="+value;
    }
}