Class Code 11/29/17

MergeSort.java

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) );
    }
}

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) );

}

Hi There!

MergeSort.java