Java Algorithm: Merge() and MergeSort()

-----------------------------------

NOTE: ONLY fill in the TODO part, then provide explanation. Do NOT change codes outside of the Merge() and MergeSort() method.

The following source code:

------------------------------------

public class LAB1 {

// TODO: document this method public static int[] insertionSort(int[] a) { //TODO: implement this method for (int i = 1; i < a.length; i++) { int element = a[i]; int j = i; while (j > 0 && a[j -1] > element){ a[j] = a[j -1]; j--; } a[j] = element; } return a; }

// TODO: document this method public static int[] mergeSort(int[] a) { //TODO: implement this method return null; }

//Subroutine to merge two subarrays public static int[] merge(int[] a1, int[] a2) { //TODO: implement this method return null; }

/******************************************** * * Do NOT modify anything below * ********************************************/

public final static int MAX_INPUT = 524287; public final static int MIN_INPUT = 0;

/* Implementation note: The "system" sorting algorithm is a Dual-Pivot Quicksort * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. * This algorithm offers O(n log(n)) performance on many data * sets that cause other quicksorts to degrade to quadratic performance, * and is typically faster than traditional (one-pivot) Quicksort implementations. */

public static int[] systemSort(int[] a) { Arrays.sort(a); return a; }

// read ints from a Scanner // returns an array of the ints read private static int[] getInts(Scanner s) { ArrayList a = new ArrayList();

while (s.hasNextInt()) { int i = s.nextInt(); if ((i <= MAX_INPUT) && (i >= MIN_INPUT)) a.add(i); }

return toIntArray(a); }

// copies an ArrayList of Integer to an array of int private static int[] toIntArray(ArrayList a) { int[] ret = new int[a.size()]; for(int i = 0; i < ret.length; i++) ret[i] = a.get(i); return ret; }

public static void main(String[] args) { Scanner s = new Scanner(System.in);

System.out.printf("Enter the sorting algorithm to use ([i]nsertion, [m]erge, or [s]ystem): "); char algo = s.next().charAt(0);

System.out.printf("Enter the integers that you would like sorted, followed by a non-integer character: "); int[] unsorted_values = getInts(s); int[] sorted_values = {};

s.close();

switch (algo) { case 'm': sorted_values = mergeSort(unsorted_values); break; case 'i': sorted_values = insertionSort(unsorted_values); break; case 's': sorted_values = systemSort(unsorted_values); break; default: System.out.println("Invalid sorting algorithm"); System.exit(0); break; }

System.out.println(Arrays.toString(sorted_values)); }

}