mmayoub

School, 12.09.2017, Ex8, merge sorting

Sep 12th, 2017
161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. public class Ex08 {
  3.     public static int[] copy(int[] arr, int start, int end) {
  4.         int[] res = new int[end - start + 1];
  5.  
  6.         for (int i = 0; i < res.length; i++) {
  7.             res[i] = arr[start + i];
  8.         }
  9.  
  10.         return res;
  11.     }
  12.  
  13.     public static int[] merge(int[] arr1, int[] arr2) {
  14.         int[] res = new int[arr1.length + arr2.length];
  15.         int p1 = 0;
  16.         int p2 = 0;
  17.         int p3 = 0;
  18.  
  19.         while (p1 < arr1.length && p2 < arr2.length) {
  20.             if (arr1[p1] <= arr2[p2]) {
  21.                 res[p3] = arr1[p1];
  22.                 p1 += 1;
  23.                 p3 += 1;
  24.             } else {
  25.                 res[p3] = arr2[p2];
  26.                 p2 += 1;
  27.                 p3 += 1;
  28.             }
  29.         }
  30.  
  31.         while (p1 < arr1.length) {
  32.             res[p3] = arr1[p1];
  33.             p1 += 1;
  34.             p3 += 1;
  35.         }
  36.  
  37.         while (p2 < arr2.length) {
  38.             res[p3] = arr2[p2];
  39.             p2 += 1;
  40.             p3 += 1;
  41.         }
  42.  
  43.         System.out.println(asString(arr1) + " and " + asString(arr2) + " was merged to " + asString(res));
  44.         return res;
  45.     }
  46.  
  47.     public static int[] mergeSort(int[] arr) {
  48.         System.out.println("start sorting " + asString(arr));
  49.         if (arr.length == 1) {
  50.             System.out.println(asString(arr) + " was sorted " + asString(arr));
  51.             return arr;
  52.         }
  53.  
  54.         int mid = arr.length / 2;
  55.         int[] left = copy(arr, 0, mid - 1);
  56.         int[] right = copy(arr, mid, arr.length - 1);
  57.         int[] res;
  58.         // sort . . . .
  59.         int[] sortedLeft = mergeSort(left);
  60.         int[] sortedRight = mergeSort(right);
  61.  
  62.         res = merge(sortedLeft, sortedRight);
  63.         System.out.println(asString(arr) + " was sorted " + asString(res));
  64.         return res;
  65.     }
  66.  
  67.     public static String asString(int[] arr) {
  68.         String res = "[";
  69.         for (int i = 0; i < arr.length; i++) {
  70.             res += arr[i] + " ";
  71.         }
  72.  
  73.         res += "]";
  74.  
  75.         return res;
  76.     }
  77.  
  78.     public static void main(String[] args) {
  79.         int[] arr = { 1, 90, 2, 21, 9, 13, 1, 2, 4 };
  80.         int[] res; // = {1, 1, 2, 4,5,6,7,8,9,13,21,90};
  81.  
  82.         System.out.println("source data : " + asString(arr));
  83.         res = mergeSort(arr);
  84.         System.out.println("the sorted data : " + asString(res));
  85.  
  86.     }
  87.  
  88. }
RAW Paste Data