Advertisement
rishu110067

Untitled

Jan 27th, 2022
919
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     static ArrayList<Integer> merge_sort(ArrayList<Integer> arr) {
  2.         // Write your code here.
  3.        merge_sort_helper(arr, 0, arr.size()-1);
  4.         return arr;
  5.     }
  6.    
  7.     static  void merge_sort_helper(ArrayList<Integer> arr, int start, int end) {
  8.         ArrayList<Integer> auxList = new ArrayList<>();
  9.         // Base Case
  10.         if(start == end) {
  11.             return;
  12.         }
  13.        
  14.         // Recursive case
  15.         int mid = start + (end - start) /2;
  16.         merge_sort_helper(arr, start, mid);
  17.         merge_sort_helper(arr, mid+1, end);
  18.        
  19.         // Merge sub-list
  20.         int i=start;
  21.         int j=mid+1;
  22.        
  23.         while(i<=mid && j<=end) {
  24.             if(arr.get(i) <= arr.get(j)) {
  25.                 auxList.add(arr.get(i));
  26.                 i++;
  27.             } else {
  28.                 auxList.add(arr.get(j));
  29.                 j++;
  30.             }
  31.         }
  32.         while(i<=mid) {
  33.             auxList.add(arr.get(i));
  34.              i++;
  35.         }
  36.         while(j<=end) {
  37.             auxList.add(arr.get(j));
  38.             j++;
  39.         }
  40.        
  41.         for(int idx = start; idx <= end; idx++) {
  42.             arr.set(idx, auxList.get(idx - start));
  43.         }
  44.     }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement