daily pastebin goal
21%
SHARE
TWEET

Untitled

a guest Jan 18th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Static  int[] mergeSort(int[] lst) {
  2.     int n = lst.length;
  3.     int[] left;
  4.     int[] right;
  5.    
  6.     // create space for left and right subarrays
  7.     if (n % 2 == 0) {
  8.         left = new int[n/2];
  9.         right = new int[n/2];
  10.     }
  11.     else {
  12.         left = new int[n/2];
  13.         right = new int[n/2+1];
  14.     }
  15.    
  16.     // fill up left and right subarrays
  17.     for (int i = 0; i < n; i++) {
  18.         if (i < n/2) {
  19.             left[i] = lst[i];
  20.         }
  21.         else {
  22.             right[i-n/2] = lst[i];
  23.         }
  24.     }
  25.    
  26.     // recursively split and merge
  27.     left = mergeSort(left);
  28.     right = mergeSort(right);
  29.    
  30.     // merge
  31.     return merge(left, right);
  32. }
  33. // the function for merging two sorted arrays
  34. static int[] merge(int[] left, int[] right) {
  35.     // create space for the merged array
  36.     int[] result = new int[left.length+right.length];
  37.    
  38.     // running indices
  39.     int i = 0;
  40.     int j = 0;
  41.     int index = 0;
  42.    
  43.     // add until one subarray is deplete
  44.     while (i < left.length && j < right.length) {
  45.         if (left[i] < right[j]) {
  46.             result[index++] = left[i++];
  47.         {
  48.         else {
  49.             result[index++] = right[j++];
  50.         }
  51.     }
  52.    
  53.     // add every leftover elelment from the subarray
  54.     while (i < left.length) {
  55.         result[index++] = left[i++];
  56.     }
  57.    
  58.     // only one of these two while loops will be executed
  59.     while (j < right.length) {
  60.         result[index++] = right[j++];
  61.     }
  62.    
  63.     return result;
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top