Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
import java.util.*;
import java.io.*;

class Solution {

static void merge(int[] arr,int l,int mid,int r){

 int n1 = mid - l +1;
 int n2 = r - mid;

 //Copy of the array 

 int[] arr1 = new int[n1];
 int[] arr2 = new int[n2];

 //1st array range is : [l---mid]

 int index = 0;
 for(int i=l;i<=mid;i++){
  arr1[index] = arr[i];
  index++;
 }

 index=0;
 for(int i=mid+1;i<=r;i++){
  arr2[index] = arr[i];
  index++;
 }

 //Same merge Logic

 int index1 = 0;
 int index2 = 0;

 int ansIndex = l;

 while(index1<n1 && index2<n2){ //Util there are values in both array

  if(arr1[index1]<arr2[index2]){
   arr[ansIndex] = arr1[index1];
   index1++;
  }else{
   arr[ansIndex] = arr2[index2];
   index2++;
  }
  ansIndex++; 
 } //This while loop will run until there are element of the arrays


 //Copying the elements of the reaming array into my ansArray

 while(index1<n1){
  arr[ansIndex++] = arr1[index1++];
 }

 while(index2<n2){
  arr[ansIndex++] = arr2[index2++];
 }

 return;
 
}


public void mergeSort(int[] arr,int l,int r){

 if(r==l){ //1 element case
  return;
 }

 int mid = (l+r)/2;

 mergeSort(arr,l,mid);
 mergeSort(arr,mid+1,r);


 //mergeSort function would have sorted the array 
 //1st array (l,mid) has been sorted
 //2nd array (mid+1,r) has also been sorted
 
 merge(arr,l,mid,r);
 
}

}
public class Main {
    public static void main(String args[]) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i= 0; i < n; i++)
            a[i] = input.nextInt();
        Solution Obj = new Solution();
        Obj.mergeSort(a,0,n-1);
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
    }
}