We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
importjava.util.Scanner;publicclassInsertionSort{staticlongmergeSort(int[]arr,int[]temp,intleft,intright){longshifts=0;if(left<right){intmid=(left+right)/2;shifts+=mergeSort(arr,temp,left,mid);shifts+=mergeSort(arr,temp,mid+1,right);shifts+=merge(arr,temp,left,mid,right);}returnshifts;}staticlongmerge(int[]arr,int[]temp,intleft,intmid,intright){longshifts=0;inti=left;intj=mid+1;intk=left;while(i<=mid&&j<=right){if(arr[i]<=arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];shifts+=mid-i+1;// Count shifts during merge}}while(i<=mid){temp[k++]=arr[i++];}while(j<=right){temp[k++]=arr[j++];}// Copy the merged elements back to the original arrayfor(i=left;i<=right;i++){arr[i]=temp[i];}returnshifts;}publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// Read the number of queriesintq=scanner.nextInt();for(intquery=0;query<q;query++){// Read the length of the arrayintn=scanner.nextInt();// Read the array elementsint[]arr=newint[n];for(inti=0;i<n;i++){arr[i]=scanner.nextInt();}// Temporary array for merge sortint[]temp=newint[n];// Call the mergeSort function and print the resultlongresult=mergeSort(arr,temp,0,n-1);System.out.println(result);}scanner.close();}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Insertion Sort Advanced Analysis
You are viewing a single comment's thread. Return to all comments →