Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private static void mergeSort(int[] arr,int begin,int end){
- if(begin>=end)
- return;
- int middle=(begin+end)/2;
- mergeSort(arr,begin,middle); //first half
- mergeSort(arr,middle+1,end); // second half
- mergeHalves(arr,begin,middle,end);
- }
- private static void mergeHalves(int[] arr,int begin,int middle,int end){
- int firstContainerStorageLimit=middle-begin+1;
- int[] firstContainer=new int[firstContainerStorageLimit];
- int secondContainerStorageLimit=end-middle;
- int[] secondContainer=new int[secondContainerStorageLimit];
- //Copy data from original array to first container
- for(int i=0;i<firstContainerStorageLimit;i++)
- firstContainer[i]=arr[begin+i];
- //Copy data from original to second container
- for(int i=0;i<secondContainerStorageLimit;i++){
- secondContainer[i]=arr[middle+1+i];
- }
- int sortedContainerIndex=begin;
- int i=0,j=0;
- while(i<firstContainerStorageLimit && j<secondContainerStorageLimit){
- if(firstContainer[i] <= secondContainer[j]){
- arr[sortedContainerIndex]=firstContainer[i];
- i++;
- }
- else{
- arr[sortedContainerIndex]=secondContainer[j];
- j++;
- }
- sortedContainerIndex++;
- }
- while(i<firstContainerStorageLimit)
- {
- arr[sortedContainerIndex++]=firstContainer[i];
- i++;
- }
- while(j<secondContainerStorageLimit){
- arr[sortedContainerIndex++]=secondContainer[j];
- j++;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement