MergeSort.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.util.stream.IntStream; import java.util.stream.Collectors; import java.util.Random; public class MergeSort { /* @pre ... * @post ... */ // precondition: leftArr and rightArr are sorted. // postcondition: outArr is sorted, merged result of leftArr, rightArr. private static void merge (int[] outArr, int[] leftArr, int[] rightArr) { // leftArr index int i = 0; // rightArr index int j = 0; // outArr index int k = 0; // Idea: While there's still data in left or right, // do a comparison between leftArr[i] and rightArr[j] // putting the smaller element in outArr[k]. // Once either leftArr or rightArr is empty, copy the // rest of the contents of the opposite array to outArr. while (i < leftArr.length && j < rightArr.length){ if (leftArr[i] < rightArr[j]) outArr[k++] = leftArr[i++]; else outArr[k++] = rightArr[j++]; } while (i < leftArr.length) outArr[k++] = leftArr[i++]; while (j < rightArr.length) outArr[k++] = rightArr[j++]; } public static void mergeSort(int[] arr){ if (arr.length > 1) { int mid = arr.length / 2; int[] leftArr = new int[mid]; int[] rightArr = new int[arr.length-mid]; System.arraycopy(arr,0,leftArr,0,mid); System.arraycopy(arr,mid,rightArr,0,arr.length-mid); mergeSort(leftArr); mergeSort(rightArr); merge(arr,leftArr,rightArr); } } public static void printArr(int[] arr){ System.out.println(IntStream.of(arr) .boxed() .map(Object::toString) .collect(Collectors.joining(", "))); } public static int[] getRandoms(int count){ return new Random().ints().limit(count).toArray(); } public static void main(String[] args){ int[] arr = {38, 27, 43, 3, 9, 82, 10}; printArr(arr); mergeSort(arr); printArr(arr); int[] randoms = getRandoms(40000000); long startTime = System.currentTimeMillis(); mergeSort(randoms); long endTime = System.currentTimeMillis(); System.out.println("Total sort of random data execution time: " + (endTime - startTime) ); } } |