Sorting Algorithms homework

runner.java

public class runner {
  public static void main(String[] args) {

    // Create an array of length 50
    int[] arr = new int[9000];
    // Fill arr with random numbers in the range 0-99:
    for (int x = 0; x < arr.length; x++) {
      arr[x] = (int)(Math.random() * 100);
    }

    printArray(arr);

    long start = System.currentTimeMillis();
    printArray(insertionSort(arr));
    long insertionTime = System.currentTimeMillis() - start;
    printArray(selectionSort(arr));
    long selectionTime = System.currentTimeMillis() - insertionTime - start;
    printArray(mergeSort(arr));
    long mergeTime = System.currentTimeMillis() - selectionTime - insertionTime - start;
    System.out.println("Times:");
    System.out.println("Insertion: " + insertionTime + " Selection: " + selectionTime + " Merge: " + mergeTime);
  }

  public static int[] mergeSort(int input[]) {
    mergeSortRecursiveInit(input, 0, input.length - 1);
    return input;
  }

  public static void mergeSortRecursiveInit(int arr[], int l, int r) {
    if (l < r) {
      // Find the middle point
      int m = l + (r - l) / 2;

      // Sort first and second halves
      mergeSortRecursiveInit(arr, l, m);
      mergeSortRecursiveInit(arr, m + 1, r);

      // Merge the sorted halves
      mergeSortRecursive(arr, l, m, r);
    }
  }

  public static void mergeSortRecursive(int arr[], int l, int m, int r) {
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int[n1];
    int R[] = new int[n2];

    /*Copy data to temp arrays*/
    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1 + j];

    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarray array
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
  }



  public static int[] insertionSort(int input[]) {
    int n = input.length;
    for (int i = 1; i < n; ++i) {
        int key = input[i];
        int j = i - 1;

        /* Move elements of arr[0..i-1], that are
           greater than key, to one position ahead
           of their current position */
        while (j >= 0 && input[j] > key) {
          input[j + 1] = input[j];
            j = j - 1;
        }
        input[j + 1] = key;
    }

    return input;
  }

  public static int[] selectionSort(int input[]) {
    int n = input.length;

    // One by one move boundary of unsorted subarray
    for (int i = 0; i < n-1; i++)
    {
      // Find the minimum element in unsorted array
      int min_idx = i;
      for (int j = i+1; j < n; j++)
        if (input[j] < input[min_idx])
          min_idx = j;

      // Swap the found minimum element with the first
      // element
      int temp = input[min_idx];
      input[min_idx] = input[i];
      input[i] = temp;
    }
    return input;
  }

  public static void printArray(int arr[]) {
    String output = "[";
    for (int x : arr) {
      output += x + ",";
    }
    output = output.substring(0, output.length() - 1);
    output += "]";
    System.out.println(output);
  }

}