Untitled
unknown
plain_text
2 years ago
1.8 kB
6
Indexable
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] + " "); } }
Editor is loading...