import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;

/**
* Your implementation of various sorting algorithms.
*
*/

/**
* Implement insertion sort.
*
* It should be:
* in-place
* stable
*
* Have a worst case running time of:
* O(n^2)
*
* And a best case running time of:
* O(n)
*
* @throws IllegalArgumentException if the array or comparator is null
* @param <T> data type to sort
* @param arr the array that must be sorted after the method runs
* @param comparator the Comparator used to compare the data in arr
*/
public static <T> void insertionSort(T[] arr, Comparator<T> comparator) {

   if(arr == null || comparator == null){
         throw new IllegalArgumentException("Cannot sort null data structure.");
   }

   T data;
   int j;
   for(int i = 1; i < arr.length; i++){
         data = arr[i];
         j = i-1;
         while (j >= 0 && comparator.compare(arr[j], data) >= 0){
            arr[j+1] = arr[j];
            j--;
         }
         arr[j + 1] = data;
   }
}

/**
* Implement selection sort.
*
* It should be:
* in-place
* unstable
*
* Have a worst case running time of:
* O(n^2)
*
* And a best case running time of:
* O(n^2)
*
* @throws IllegalArgumentException if the array or comparator is null
* @param <T> data type to sort
* @param arr the array that must be sorted after the method runs
* @param comparator the Comparator used to compare the data in arr
*/
public static <T> void selectionSort(T[] arr, Comparator<T> comparator) {

   if(arr == null || comparator == null){
         throw new IllegalArgumentException("Cannot sort null data structure.");
   }

   int minIdx;

   for(int i=0; i<arr.length-1; i++) {
         minIdx = i;
         for(int j=i+1; j<arr.length; j++) {
            if(comparator.compare(arr[j], arr[minIdx]) < 0) {
               minIdx = j;
            }
         }
         T tmp = arr[minIdx];
         arr[minIdx] = arr[i];
         arr[i] = tmp;
   }
}

/**
* Implement merge sort.
*
* It should be:
* out-of-place
* stable
*
* Have a worst case running time of:
* O(n log n)
*
* And a best case running time of:
* O(n log n)
*
* You can create more arrays to run mergesort, but at the end, everything
* should be merged back into the original T[] which was passed in.
*
* When splitting the array, if there is an odd number of elements, put the
* extra data on the right side.
*
* @throws IllegalArgumentException if the array or comparator is null
* @param <T> data type to sort
* @param arr the array to be sorted
* @param comparator the Comparator used to compare the data in arr
*/
public static <T> void mergeSort(T[] arr, Comparator<T> comparator) {

   if(arr == null || comparator == null){
         throw new IllegalArgumentException("Cannot sort null data structure.");
   }

   mergeSort(arr, comparator, 0, arr.length-1);
}

/**
* This function is the helper function for mergeSort.
* It takes additional left and right indexes.
* @param <T> data type to sort
* @param arr the array to be sorted
* @param comparator the Comparator used to compare the data in arr
* @param l left index
* @param r right index
*/
private static <T> void mergeSort(T[] arr, Comparator<T> comparator, int l, int r) {
   if(l < r){
         int s = r - l;
         if(s % 2 == 1){
            int mid = l + (r-l)/2;
            mergeSort(arr, comparator, l, mid);
            mergeSort(arr, comparator, mid+1, r);
            merge(arr, comparator, l, mid

Concepts: • Inheritance • Multiple Classes • Generics • Threads...