Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package mergeSort;
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.util.Scanner;
- import java.util.Arrays;
- public class MS_external {
- @SuppressWarnings("resource")
- public static void main(String args[]) throws FileNotFoundException {
- System.out.println("Size of data; Time taken to sort (ms)");
- File fin = new File ("fileToSort.txt");
- Scanner stream = new Scanner(fin);
- for(int i = 100000; i <= 10000000; i+= 100000) {
- //create array, fill with data
- int[] sortMe = new int[i];
- for (int j = 0; j < sortMe.length; j++) {
- sortMe[j] = stream.nextInt();
- }
- //get time start
- long timeStart = System.currentTimeMillis();
- mergeSort(sortMe, sortMe.length);
- long timeEnd = System.currentTimeMillis();
- //calc time to sort
- long totalTime = timeEnd - timeStart;
- System.out.println(i + "; " + totalTime + "ms");
- }
- }
- public static void merge( int[] a, int[] l, int[] r, int leftSize, int rightSize) {
- //setup loop variables
- int i = 0, j = 0, k = 0;
- //sort while the bottom or top haven't been exhausted
- while (i < leftSize && j < rightSize) {
- //if left el @i is less than right el @j
- if (l[i] <= r[j]) {
- //update element for a
- a[k] = l[i];
- //increment pointers
- k++;
- i++;
- }
- else {
- //else use the other element
- a[k] = r[j];
- //increment pointers
- k++;
- j++;
- }
- }
- //continue through all elements and add to a
- while (i < leftSize) {
- a[k] = l[i];
- k++;
- i++;
- }
- //continue through all elements and add to a
- while (j < rightSize) {
- a[k] = r[j];
- k++;
- j++;
- }
- }
- public static void mergeSort(int[] a, int n) {
- //if there's one item, it's already sorted
- if (n < 2) {
- return;
- }
- //calculate the middle index from n/2
- int middleIndex = n / 2;
- //create new arrays for left and right, half and half
- int[] l = new int[middleIndex];
- int[] r = new int[n - middleIndex];
- //copy first half of a into left array
- for (int i = 0; i < middleIndex; i++) {
- l[i] = a[i];
- }
- //copy second half of a into right array
- for (int i = middleIndex; i < n; i++) {
- r[i - middleIndex] = a[i];
- }
- //sort the left half
- mergeSort(l, middleIndex);
- //sort the right half
- mergeSort(r, n - middleIndex);
- //merge the arrays
- merge(a, l, r, middleIndex, n - middleIndex);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement