MergeSort.java

import java.util.Arrays;

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

public static void sort(int[] A,int p,int r){
if(p<r){
int q = (p+r)/2;
sort(A,p,q);
sort(A,q+1,r);
sort(A,p,q,r);
}
}

//p<=q<r,no check
public static void sort(int[] A,int p,int q,int r){
int[] L = new int[q-p+2];
for(int i=p;i<=q;i++){
L[i-p] = A[i];
}
int[] R = new int[r-q+1];
for(int i=q+1;i<=r;i++){
R[i-q-1] = A[i];
}
L[L.length-1] = Integer.MAX_VALUE;
R[R.length-1] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for(int k=p;k<=r;k++){
if(L[i]<=R[j]){
A[k] = L[i];
i++;
}
else{
A[k] = R[j];
j++;
}
}
}
}