Class Code 4/30/18 - Merge Sort - Daniel R. Schlegel

MergeSort.java

import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.Random;

public class MergeSort {

    // Precondition: leftArr and rightArr are sorted.
    // Postcondition: outArr is the sorted, merged result of leftArr and rightArr.
    private static void merge(int[] outArr, int[] leftArr, int[] rightArr) {
        // leftArr index
        int l = 0;
        // rightArr index
        int r = 0;
        // outArr index
        int o = 0;

        // Idea: While there are still data in left and right,
        //       do a comparison between leftArr[l] and rightArr[r]
        //       putting the lesser element in outArr[o] and incrementing
        //       indices as appropriate. Once either leftArr or rightArr
        //       is empty, copy the rest of the contents of the opposite
        //       array into outArr.
        while (l < leftArr.length && r < rightArr.length){
            if (leftArr[l] < rightArr[r])
                outArr[o++] = leftArr[l++];
            else
                outArr[o++] = rightArr[r++];
        }

        while (l < leftArr.length)
            outArr[o++] = leftArr[l++];

        while (r < rightArr.length)
            outArr[o++] = rightArr[r++];
    }

    public static void mergeSort(int[] arr){
        // Recursively split the array until size is 1. 
        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){
        // Testing merge.
        int left[] = {1,3,5,6,7};
        int right[] = {1,2,3,4};
        int out[] = new int[9];

        merge(out, left, right);

        printArr(out);

        // Testing mergeSort. 
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        printArr(arr);
        mergeSort(arr);
        printArr(arr);

        // Sorting benchmarks
        int[] randoms = getRandoms(10000000);
        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 {

// Precondition: leftArr and rightArr are sorted.

// Postcondition: outArr is the sorted, merged result of leftArr and rightArr.

private static void merge(int[] outArr, int[] leftArr, int[] rightArr) {

// leftArr index

int l = 0;

// rightArr index

int r = 0;

// outArr index

int o = 0;

// Idea: While there are still data in left and right,

// do a comparison between leftArr[l] and rightArr[r]

// putting the lesser element in outArr[o] and incrementing

// indices as appropriate. Once either leftArr or rightArr

// is empty, copy the rest of the contents of the opposite

// array into outArr.

while (l < leftArr.length && r < rightArr.length){

if (leftArr[l] < rightArr[r])

outArr[o++] = leftArr[l++];

else

outArr[o++] = rightArr[r++];

}

while (l < leftArr.length)

outArr[o++] = leftArr[l++];

while (r < rightArr.length)

outArr[o++] = rightArr[r++];

}

public static void mergeSort(int[] arr){

// Recursively split the array until size is 1.

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

// Testing merge.

int left[] = {1,3,5,6,7};

int right[] = {1,2,3,4};

int out[] = new int[9];

merge(out, left, right);

printArr(out);

// Testing mergeSort.

int[] arr = {38, 27, 43, 3, 9, 82, 10};

printArr(arr);

mergeSort(arr);

printArr(arr);

// Sorting benchmarks

int[] randoms = getRandoms(10000000);

long startTime = System.currentTimeMillis();

mergeSort(randoms);

long endTime = System.currentTimeMillis();

System.out.println("Total sort of random data execution time: " + (endTime - startTime) );

}

Hi There!

Class Code 4/30/18 – Merge Sort

MergeSort.java