O(nlogn) Sorting Algorithms

MergeSort.java

import java.util.stream.Collectors;
import java.util.Arrays;

public class MergeSort<E extends Comparable<E>> {
 
    // Precondition: leftArr and rightArr are sorted.
    // Postcondition: outArr is the sorted, merged result of leftArr and rightArr.
    private void merge(E[] outArr, E[] leftArr, E[] 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].compareTo(rightArr[r]) < 0)
                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 void mergeSort(E[] arr){
        // Recursively split the array in half, until size is 1
        if (arr.length > 1){
        // -- Find the midpoint of arr
            int mid = arr.length / 2;
        // -- Create a left and right array
            E[] leftArr = (E[]) new Comparable[mid];
            E[] rightArr = (E[]) new Comparable[arr.length - mid];
        // -- Populate them
            System.arraycopy(arr, 0, leftArr, 0, mid);
            System.arraycopy(arr, mid, rightArr, 0, arr.length - mid);
        // -- Recursive call to mergeSort on left, right
            mergeSort(leftArr);
            mergeSort(rightArr);
        // -- Merge left and right, store the result in arr
            merge(arr, leftArr, rightArr);
        }
    }

    public void printArr(E[] arr){
        System.out.println(Arrays.stream(arr)
                                 .map(Object::toString)
                                 .collect(Collectors.joining(", ")));
    }


    public static void main(String[] args){
        MergeSort<Integer> ms = new MergeSort<>();
        
        // Testing merge.
        Integer left[] = {1,3,5,6,7};
        Integer right[] = {1,2,3,4};
        Integer out[] = new Integer[9];
        ms.merge(out, left, right);
        ms.printArr(out);

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

import java.util.stream.Collectors;

import java.util.Arrays;

public class MergeSort<E extends Comparable<E>> {

// Precondition: leftArr and rightArr are sorted.

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

private void merge(E[] outArr, E[] leftArr, E[] 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].compareTo(rightArr[r]) < 0)

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 void mergeSort(E[] arr){

// Recursively split the array in half, until size is 1

if (arr.length > 1){

// -- Find the midpoint of arr

int mid = arr.length / 2;

// -- Create a left and right array

E[] leftArr = (E[]) new Comparable[mid];

E[] rightArr = (E[]) new Comparable[arr.length - mid];

// -- Populate them

System.arraycopy(arr, 0, leftArr, 0, mid);

System.arraycopy(arr, mid, rightArr, 0, arr.length - mid);

// -- Recursive call to mergeSort on left, right

mergeSort(leftArr);

mergeSort(rightArr);

// -- Merge left and right, store the result in arr

merge(arr, leftArr, rightArr);

}

public void printArr(E[] arr){

System.out.println(Arrays.stream(arr)

.map(Object::toString)

.collect(Collectors.joining(", ")));

}

public static void main(String[] args){

MergeSort<Integer> ms = new MergeSort<>();

// Testing merge.

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

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

Integer out[] = new Integer[9];

ms.merge(out, left, right);

ms.printArr(out);

// Testing mergeSort.

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

ms.printArr(arr);

ms.mergeSort(arr);

ms.printArr(arr);

}

QuickSort.java

import java.util.stream.Collectors;
import java.util.Arrays;

public class QuickSort<E extends Comparable<E>>{

    private void swap(E arr[], int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // arr is the full array, we're only looking at the
    // segment from first - last.
    // We'll return the new position of the pivot element
    private int partition(E arr[], int first, int last){
        //pivot <- arr[first]
        E pivot = arr[first];
        //up <- first + 1          (i)
        int up = first + 1;
        //down <- last             (j)
        int down = last;

        /*
          As long as up < down:
              1) Compare arr[up] with the pivot element
                 incrementing up until arr[up] > pivot
              2) Compare arr[down] with the pivot element
                 decrementing down until arr[down] < pivot
              3) When up >= down
                 a) Swap the pivot with arr[down]
                 b) Return down
              4) Swap arr[up] with arr[down]
         */
        while ( true ){
            while(up < last && arr[up].compareTo(pivot) < 0)
                up++;

            while(down > first && arr[down].compareTo(pivot) > 0)
                down--;

            if (up >= down){
                swap(arr, first, down);
                return down;
            }

            swap(arr, up, down);
        }
    }

    private void quickSort(E arr[], int first, int last){
        if (first < last){
            int pivotIndex = partition(arr, first, last);
            quickSort(arr, first, pivotIndex-1);
            quickSort(arr, pivotIndex+1, last);
        }
    }

    public void quickSort(E arr[]){
        quickSort(arr, 0, arr.length-1);
    }

    public void printArr(E[] arr){
        System.out.println(Arrays.stream(arr)
                                 .map(Object::toString)
                                 .collect(Collectors.joining(", ")));
    }

    public static void main(String[] args){
        QuickSort<Integer> qs = new QuickSort<>();
        Integer[] arr = {44, 75, 23, 43, 55, 12, 64, 77, 33};
        qs.printArr(arr);
        qs.partition(arr, 0, arr.length-1);
        qs.printArr(arr);
        
        Integer[] arr2 = {44, 75, 23, 43, 55, 12, 64, 77, 33};
        qs.printArr(arr2);
        qs.quickSort(arr2);
        qs.printArr(arr2);
    }
}

import java.util.stream.Collectors;

import java.util.Arrays;

public class QuickSort<E extends Comparable<E>>{

private void swap(E arr[], int i, int j){

E temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

// arr is the full array, we're only looking at the

// segment from first - last.

// We'll return the new position of the pivot element

private int partition(E arr[], int first, int last){

//pivot <- arr[first]

E pivot = arr[first];

//up <- first + 1 (i)

int up = first + 1;

//down <- last (j)

int down = last;

As long as up < down:

1) Compare arr[up] with the pivot element

incrementing up until arr[up] > pivot

2) Compare arr[down] with the pivot element

decrementing down until arr[down] < pivot

3) When up >= down

a) Swap the pivot with arr[down]

b) Return down

4) Swap arr[up] with arr[down]

while ( true ){

while(up < last && arr[up].compareTo(pivot) < 0)

up++;

while(down > first && arr[down].compareTo(pivot) > 0)

down--;

if (up >= down){

swap(arr, first, down);

return down;

}

swap(arr, up, down);

}

private void quickSort(E arr[], int first, int last){

if (first < last){

int pivotIndex = partition(arr, first, last);

quickSort(arr, first, pivotIndex-1);

quickSort(arr, pivotIndex+1, last);

}

public void quickSort(E arr[]){

quickSort(arr, 0, arr.length-1);

}

public void printArr(E[] arr){

System.out.println(Arrays.stream(arr)

.map(Object::toString)

.collect(Collectors.joining(", ")));

}

public static void main(String[] args){

QuickSort<Integer> qs = new QuickSort<>();

Integer[] arr = {44, 75, 23, 43, 55, 12, 64, 77, 33};

qs.printArr(arr);

qs.partition(arr, 0, arr.length-1);

qs.printArr(arr);

Integer[] arr2 = {44, 75, 23, 43, 55, 12, 64, 77, 33};

qs.printArr(arr2);

qs.quickSort(arr2);

qs.printArr(arr2);

}

MergeSortBench.java

package bench;

import sort.MergeSort;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class MergeSortBench {

    @State(Scope.Thread)
    public static class ThreadState{
        MergeSort<Integer> ms;
        Integer[] data;

        private int count = 1280000;

        @Setup(Level.Invocation)
        public void prepare(){
            ms = new MergeSort<>();
            data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 3, time = 3)
    @Measurement(iterations = 3, time = 3)
    public void mergeAvgTime(ThreadState ts) {
        ts.ms.mergeSort(ts.data);
    }
    
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(MergeSortBench.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

package bench;

import sort.MergeSort;

import java.util.concurrent.TimeUnit;

import java.util.Random;

import java.util.Arrays;

import org.openjdk.jmh.annotations.Benchmark;

import org.openjdk.jmh.annotations.BenchmarkMode;

import org.openjdk.jmh.annotations.Level;

import org.openjdk.jmh.annotations.Measurement;

import org.openjdk.jmh.annotations.Mode;

import org.openjdk.jmh.annotations.OutputTimeUnit;

import org.openjdk.jmh.annotations.Scope;

import org.openjdk.jmh.annotations.Setup;

import org.openjdk.jmh.annotations.State;

import org.openjdk.jmh.annotations.Warmup;

import org.openjdk.jmh.runner.Runner;

import org.openjdk.jmh.runner.RunnerException;

import org.openjdk.jmh.runner.options.Options;

import org.openjdk.jmh.runner.options.OptionsBuilder;

public class MergeSortBench {

@State(Scope.Thread)

public static class ThreadState{

MergeSort<Integer> ms;

Integer[] data;

private int count = 1280000;

@Setup(Level.Invocation)

public void prepare(){

ms = new MergeSort<>();

data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);

}

@Benchmark

@BenchmarkMode(Mode.AverageTime)

@OutputTimeUnit(TimeUnit.MILLISECONDS)

@Warmup(iterations = 3, time = 3)

@Measurement(iterations = 3, time = 3)

public void mergeAvgTime(ThreadState ts) {

ts.ms.mergeSort(ts.data);

}

public static void main(String[] args) throws RunnerException {

Options opt = new OptionsBuilder()

.include(MergeSortBench.class.getSimpleName())

.forks(1)

.build();

new Runner(opt).run();

}

QuickSortBench.java

package bench;

import sort.QuickSort;
import java.util.concurrent.TimeUnit;
import java.util.Random;
import java.util.Arrays;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class QuickSortBench {

    @State(Scope.Thread)
    public static class ThreadState{
        QuickSort<Integer> qs;
        Integer[] data;
        private int count = 1280000;

        @Setup(Level.Invocation)
        public void prepare(){
            qs = new QuickSort<>();
            data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 3, time = 3)
    @Measurement(iterations = 3, time = 3)
    public void quickAvgTime(ThreadState ts) {
        ts.qs.quickSort(ts.data);
    }
    
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(QuickSortBench.class.getSimpleName())
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

package bench;

import sort.QuickSort;

import java.util.concurrent.TimeUnit;

import java.util.Random;

import java.util.Arrays;

import org.openjdk.jmh.annotations.Benchmark;

import org.openjdk.jmh.annotations.BenchmarkMode;

import org.openjdk.jmh.annotations.Level;

import org.openjdk.jmh.annotations.Measurement;

import org.openjdk.jmh.annotations.Mode;

import org.openjdk.jmh.annotations.OutputTimeUnit;

import org.openjdk.jmh.annotations.Scope;

import org.openjdk.jmh.annotations.Setup;

import org.openjdk.jmh.annotations.State;

import org.openjdk.jmh.annotations.Warmup;

import org.openjdk.jmh.runner.Runner;

import org.openjdk.jmh.runner.RunnerException;

import org.openjdk.jmh.runner.options.Options;

import org.openjdk.jmh.runner.options.OptionsBuilder;

public class QuickSortBench {

@State(Scope.Thread)

public static class ThreadState{

QuickSort<Integer> qs;

Integer[] data;

private int count = 1280000;

@Setup(Level.Invocation)

public void prepare(){

qs = new QuickSort<>();

data = new Random().ints().limit(count).boxed().toArray(Integer[]::new);

}

@Benchmark

@BenchmarkMode(Mode.AverageTime)

@OutputTimeUnit(TimeUnit.MILLISECONDS)

@Warmup(iterations = 3, time = 3)

@Measurement(iterations = 3, time = 3)

public void quickAvgTime(ThreadState ts) {

ts.qs.quickSort(ts.data);

}

public static void main(String[] args) throws RunnerException {

Options opt = new OptionsBuilder()

.include(QuickSortBench.class.getSimpleName())

.forks(1)

.build();

new Runner(opt).run();

}