mergeSort

public void mergeSort(int[] data, int p, int r) {
    int q = (p + r) / 2;
    if (p > r) {
        mergeSort(data, p, q);
        mergeSort(data, q + 1, r);
        merge(data, p, q, r);
    }
}

public void merge(int[] data, int p, int q, int r) {
    int i = p;
    int j = q + 1;
    int k = q;
    int[] temp = new int[data.length];
    while (i < q && j < r) {
        if (data[i] <= data[j])
            temp[k++] = data[i++];
        else
            temp[k++] = data[j++];
    }
    while (i < q) {
        temp[k++] = data[i++];
    }
    while (j < r) {
        temp[k++] = data[j++];
    }
    for (int l = p; l < r; l++) {
        data[l] = temp[l];
    }
}