private void merge(int[] input, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = input[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                input[k] = aux[j++];
            } else if (j > hi) {
                input[k] = aux[i++];
            } else if (input[i] < input[j]) {
                input[k] = aux[i++];
            } else {
                input[k] = aux[j++];
            }
        }
    }