SHARE
TWEET

Untitled

a guest Dec 9th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. package mergeSort;
  3. import java.io.File;
  4. import java.io.FileNotFoundException;
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7.  
  8.  
  9. public class MS_external {
  10.     @SuppressWarnings("resource")
  11.     public static void main(String args[]) throws FileNotFoundException {
  12.        
  13.         System.out.println("Size of data; Time taken to sort (ms)");
  14.        
  15.         File fin = new File ("fileToSort.txt");
  16.         Scanner stream = new Scanner(fin);
  17.        
  18.         for(int i = 100000; i <= 10000000; i+= 100000) {
  19.            
  20.             //create array, fill with data
  21.             int[] sortMe = new int[i];
  22.             for (int j = 0; j < sortMe.length; j++) {
  23.                 sortMe[j] = stream.nextInt();
  24.             }
  25.            
  26.             //get time start
  27.             long timeStart = System.currentTimeMillis();
  28.             mergeSort(sortMe, sortMe.length);
  29.             long timeEnd = System.currentTimeMillis();
  30.             //calc time to sort
  31.             long totalTime = timeEnd - timeStart;
  32.            
  33.             System.out.println(i + "; " + totalTime + "ms");
  34.            
  35.         }
  36.        
  37.        
  38.     }
  39.    
  40.     public static void merge( int[] a, int[] l, int[] r, int leftSize, int rightSize) {
  41.              
  42.                 //setup loop variables
  43.                 int i = 0, j = 0, k = 0;
  44.                
  45.                 //sort while the bottom or top haven't been exhausted
  46.                 while (i < leftSize && j < rightSize) {
  47.                     //if left el @i is less than right el @j
  48.                     if (l[i] <= r[j]) {
  49.                         //update element for a
  50.                         a[k] = l[i];
  51.                         //increment pointers
  52.                         k++;
  53.                         i++;
  54.                     }
  55.                     else {
  56.                         //else use the other element
  57.                         a[k] = r[j];
  58.                         //increment pointers
  59.                         k++;
  60.                         j++;
  61.                     }
  62.                 }
  63.                
  64.                 //continue through all elements and add to a
  65.                 while (i < leftSize) {
  66.                     a[k] = l[i];
  67.                     k++;
  68.                     i++;
  69.                 }
  70.                
  71.                 //continue through all elements and add to a
  72.                 while (j < rightSize) {
  73.                     a[k] = r[j];
  74.                     k++;
  75.                     j++;
  76.                 }
  77.                
  78.             }
  79.    
  80.     public static void mergeSort(int[] a, int n) {
  81.        
  82.        
  83.         //if there's one item, it's already sorted
  84.         if (n < 2) {
  85.             return;
  86.         }
  87.        
  88.         //calculate the middle index from n/2
  89.         int middleIndex = n / 2;
  90.        
  91.         //create new arrays for left and right, half and half
  92.         int[] l = new int[middleIndex];
  93.         int[] r = new int[n - middleIndex];
  94.        
  95.         //copy first half of a into left array
  96.         for (int i = 0; i < middleIndex; i++) {
  97.             l[i] = a[i];
  98.         }
  99.         //copy second half of a into right array
  100.         for (int i = middleIndex; i < n; i++) {
  101.             r[i - middleIndex] = a[i];
  102.         }
  103.        
  104.         //sort the left half
  105.         mergeSort(l, middleIndex);
  106.         //sort the right half
  107.         mergeSort(r, n - middleIndex);
  108.        
  109.        
  110.         //merge the arrays
  111.         merge(a, l, r, middleIndex, n - middleIndex);
  112.        
  113.     }
  114. }
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