Sorts.java

/* Insertion sort. Modifies the original array. */
public static void insertionSort(int[] array) {
    // Iterate starting from index 1
    for (int i = 1; i < array.length; i++) {
        int element = array[i];
        int j = i;

        // Move current element to the left by one step until it's in the right place.
        while (j > 0 && (array[j - 1] > element)) {
            array[j] = array[j - 1];
            j--;
        }

        array[j] = element;
    }
}

/* Selection sort. Modifies the original array. */
public static void selectionSort(int[] array) {
    int minimumIndex;
    for (int i = 0; i < array.length; i++) {
        minimumIndex = i;

        // Find the minimum
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minimumIndex]) {
                minimumIndex = j;
            }
        }

        // Swap if needed
        if (minimumIndex != i) {
            int temp = array[i];
            array[i] = array[minimumIndex];
            array[minimumIndex] = temp;
        }
    }
}

/* Mergesort. Modifies the original array. */
public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int midpoint = n / 2;
    int[] left = new int[midpoint];
    int[] right = new int[n - midpoint];
    for (int i = 0; i < midpoint; i++) {
        left[i] = array[i];
    }
    for (int i = midpoint; i < n; i++) {
        right[i - midpoint] = array[i];
    }
    mergeSort(left);
    mergeSort(right);
    int i = 0;
    int j = 0;
    int counter = 0;
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            array[counter] = left[i];
            i++;
        } else {
            array[counter] = right[j];
            j++;
        }
        counter++;
    }
    while (i < left.length) {
        array[counter] = left[i];
        i++;
        counter++;
    }
    while (j < right.length) {
        array[counter] = right[j];
        j++;
        counter++;
    }
}