Guest User

Untitled

a guest
Feb 11th, 2017
130
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class ArrayMerger {
  2.  
  3.     private int[] aux;
  4.     private int[] array;
  5.  
  6.     private int leftArrayIndex;
  7.     private int rightArrayIndex;
  8.     private int arrayIndex;
  9.  
  10.     private int leftSubArrayEnd;
  11.     private int rightSubArrayEnd;
  12.  
  13.     public ArrayMerger(int[] array) {
  14.         this.array = array;
  15.         this.aux = new int[array.length];
  16.     }
  17.  
  18.     private void prepareToMerge(int low, int mid, int high) {
  19.         this.arrayIndex = low;
  20.         this.leftArrayIndex = low;
  21.         this.rightArrayIndex = mid;
  22.         this.leftSubArrayEnd = mid;
  23.         this.rightSubArrayEnd = high;
  24.         System.arraycopy(array, low, aux, low, high - low);
  25.     }
  26.  
  27.     public void merge(int low, int mid, int high) {
  28.         prepareToMerge(low, mid, high);
  29.         while (hasValuesToMerge()) {
  30.             if (isRightSubArrayEmpty()) {
  31.                 takeValueFromLeftSubArray();
  32.             } else if (isLeftSubArrayEmpty()) {
  33.                 takeValueFromRightSubArray();
  34.             } else if (isValueInLeftArraySmaller()) {
  35.                 takeValueFromLeftSubArray();
  36.             } else {
  37.                 takeValueFromRightSubArray();
  38.             }
  39.         }
  40.     }
  41.  
  42.     private boolean isValueInLeftArraySmaller() {
  43.         return aux[leftArrayIndex] < aux[rightArrayIndex];
  44.     }
  45.  
  46.     private void takeValueFromLeftSubArray() {
  47.         array[arrayIndex++] = aux[leftArrayIndex++];
  48.     }
  49.  
  50.     private void takeValueFromRightSubArray() {
  51.         array[arrayIndex++] = aux[rightArrayIndex++];
  52.     }
  53.  
  54.     private boolean isRightSubArrayEmpty() {
  55.         return rightArrayIndex >= rightSubArrayEnd;
  56.     }
  57.  
  58.     private boolean isLeftSubArrayEmpty() {
  59.         return leftArrayIndex >= leftSubArrayEnd;
  60.     }
  61.  
  62.     private boolean hasValuesToMerge() {
  63.         return leftArrayIndex < leftSubArrayEnd || rightArrayIndex < rightSubArrayEnd;
  64.     }
  65.  
  66. }
RAW Paste Data