daily pastebin goal
28%
SHARE
TWEET

Untitled

a guest Mar 20th, 2017 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.blogspot.groglogs.mergesort;
  2.  
  3. public class Mergesort {
  4.  
  5.     //need to pass the res array as input since we are pass by value!
  6.     public static int[] merge(int[] res, int[] left, int[] right){
  7.         int left_idx = 0, right_idx = 0, res_idx = 0;
  8.  
  9.         if(left == null || right == null || left.length == 0 || right.length == 0) return null;
  10.  
  11.         //scan both left and right until we reach either end
  12.         //CAUTION: the indexes are the easiest part to screw up!
  13.         //DOUBLE CAUTION: we must loop BOTH arrays at the same time! We don't know how are they sorted!
  14.         while(left_idx < left.length && right_idx < right.length){
  15.             //order the elements while keeping track of the indexes
  16.             //if left is smaller than right, copy left, increase left, increase result
  17.             if(left[left_idx] <= right[right_idx]){
  18.                 res[res_idx] = left[left_idx];
  19.                 left_idx++;
  20.                 res_idx++;
  21.             }
  22.             //otherwise, copy right, increase right, increase result
  23.             else{
  24.                 res[res_idx] = right[right_idx];
  25.                 right_idx++;
  26.                 res_idx++;
  27.             }
  28.         }
  29.  
  30.         //we are still not finished, maybe we have some elements still in left or right, copy them as well
  31.         while(left_idx < left.length){
  32.             res[res_idx] = left[left_idx];
  33.             res_idx++;
  34.             left_idx++;
  35.         }
  36.  
  37.         while(right_idx < right.length){
  38.             res[res_idx] = right[right_idx];
  39.             res_idx++;
  40.             right_idx++;
  41.         }
  42.  
  43.         return res;
  44.  
  45.     }
  46.  
  47.     public static int[] sort(int[] list){
  48.         int[] left, right;
  49.  
  50.         if(list == null || list.length == 0) return null;
  51.  
  52.         //our base case, a list of a single element is already sorted
  53.         if(list.length == 1) return list;
  54.  
  55.         //split array in two halves
  56.         //fun fact: Math.floor returns a double
  57.         left  = new int[list.length - (int)Math.floor(list.length / 2)];
  58.         right = new int[list.length - left.length];
  59.  
  60.         //copy the elements in the two arrays left and right
  61.         for(int i = 0; i < left.length; i++){
  62.             left[i] = list[i];
  63.         }
  64.  
  65.         for(int i = left.length, j = 0; i < list.length; i++, j++){
  66.             right[j] = list[i];
  67.         }
  68.  
  69.         //sort both parts separately
  70.         sort(left);
  71.         sort(right);
  72.  
  73.         //then put everything together at each step
  74.         return merge(list, left, right);
  75.     }
  76.  
  77. }
RAW Paste Data
Top