jTruBela

MyMergeSort

Dec 4th, 2021
970
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package testSpace;
  2.  
  3.  
  4. public class MergeSort {
  5.  
  6.     public static int[] merge_sort (int[] array, int p, int r) {
  7.  
  8.         if (p < r) {
  9.             int q = (int) Math.floor((p+r)/2);
  10.             merge_sort(array,p,q);
  11.             merge_sort(array,q+1,r);
  12.             Merge(array,p,q,r);
  13.         }
  14.  
  15.         else if (p==r) {
  16.             print("-------------------------------\n");
  17.             print("p:" + p + " = " + "r:"+r + ": continuing\n");
  18.             print("-------------------------------\n");
  19.  
  20.         }
  21.  
  22.         return array;
  23.     }
  24.  
  25.     public static void Merge(int[] array, int p, int q, int r) {
  26.         print("***********Split start**************");
  27.         print("\n\nStarting Array: ");
  28.         print_array(array);
  29.         int n1 = q-p+1;
  30.         int n2 = r-q;
  31.  
  32.         int L[] = new int [n1+1];
  33.         int R[] = new int [n2+1];
  34.  
  35.  
  36.         for(int i = 0;i < n1;i++) {        
  37.             L[i] = array[p+i];
  38.         }  
  39.  
  40.  
  41.         for(int j = 0;j < n2;j++) {
  42.             R[j] = array[q+j+1];
  43.         }  
  44.  
  45.  
  46.         L[n1] = Integer.MAX_VALUE;
  47.         R[n2] = Integer.MAX_VALUE;
  48.         print("**********Split finish**************\n");
  49.  
  50.  
  51.        
  52.         int i = 0;
  53.         int j = 0;
  54.         int count = 0;
  55.  
  56.         for(int k = p; k<=r; k++) {
  57.             if (L[i] <= R[j]) {
  58.                 print("L[i]<=R[j]\nExchange happening\n");
  59.                 array[k] = L[i];
  60.                 i++;
  61.  
  62.             }          
  63.             else { 
  64.                 print("L[i]>R[j]\n");
  65.                 array[k] = R[j];
  66.                 j++;
  67.  
  68.  
  69.             }
  70.             count++;
  71.             print("---------------------------------");
  72.             print("\nIteration:" + count
  73.                                 + " ~ p:" +p
  74.                                 +";q:"+q
  75.                                 +";r:"+r
  76.                                 +";i:"+i
  77.                                 +";j:"+j+"\n");
  78.             print("---------------------------------");
  79.  
  80.             print("\nA Array: -- ");
  81.             print_array(array);
  82.             print("\nL Array: -- ");
  83.             print_array(L);
  84.             print("\nR Array: -- ");
  85.             print_array(R);
  86.         }
  87.         print("**********************************\n");
  88.  
  89.  
  90.     }
  91.     public static void print(String string) {
  92.         System.out.print(string);
  93.     }
  94.  
  95.     public static void print_array (int[] array) {
  96.         for (int i = 0; i < array.length; i++)
  97.             System.out.print(array[i] + ", ");
  98.         System.out.println("");
  99.     }
  100.  
  101.     public static void main(String[] args) {
  102.         int[] array = {5,2,4,7,1,3,2,6};
  103.  
  104.  
  105.         int n = array.length;
  106.  
  107.         array = merge_sort(array, 0, n-1);
  108.         print("Finish Array: ");
  109.         print_array(array);
  110.     }
  111. }
  112.  
RAW Paste Data