Advertisement
Guest User

MergeSort java

a guest
Oct 19th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. private static void mergeSort(int[] arr,int begin,int end){
  2.  
  3. if(begin>=end)
  4. return;
  5.  
  6. int middle=(begin+end)/2;
  7. mergeSort(arr,begin,middle); //first half
  8. mergeSort(arr,middle+1,end); // second half
  9. mergeHalves(arr,begin,middle,end);
  10.  
  11. }
  12.  
  13.  
  14. private static void mergeHalves(int[] arr,int begin,int middle,int end){
  15.  
  16. int firstContainerStorageLimit=middle-begin+1;
  17. int[] firstContainer=new int[firstContainerStorageLimit];
  18.  
  19. int secondContainerStorageLimit=end-middle;
  20. int[] secondContainer=new int[secondContainerStorageLimit];
  21.  
  22. //Copy data from original array to first container
  23. for(int i=0;i<firstContainerStorageLimit;i++)
  24. firstContainer[i]=arr[begin+i];
  25.  
  26. //Copy data from original to second container
  27. for(int i=0;i<secondContainerStorageLimit;i++){
  28. secondContainer[i]=arr[middle+1+i];
  29. }
  30.  
  31. int sortedContainerIndex=begin;
  32.  
  33. int i=0,j=0;
  34.  
  35. while(i<firstContainerStorageLimit && j<secondContainerStorageLimit){
  36.  
  37. if(firstContainer[i] <= secondContainer[j]){
  38. arr[sortedContainerIndex]=firstContainer[i];
  39. i++;
  40. }
  41. else{
  42. arr[sortedContainerIndex]=secondContainer[j];
  43. j++;
  44. }
  45.  
  46. sortedContainerIndex++;
  47. }
  48.  
  49. while(i<firstContainerStorageLimit)
  50. {
  51. arr[sortedContainerIndex++]=firstContainer[i];
  52. i++;
  53. }
  54.  
  55. while(j<secondContainerStorageLimit){
  56. arr[sortedContainerIndex++]=secondContainer[j];
  57. j++;
  58. }
  59.  
  60.  
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement