import java.util.ArrayList;

public class Merge_Sort {
    static ArrayList<Integer> merge_sort(ArrayList<Integer> arr) {

        help(arr, 0, arr.size() -1);
        return arr;
    }
    static void help(ArrayList<Integer> arr, int start, int end){
        if(start >= end){
            return;
        }
        int i = start;
        int mid = (start + end) / 2;
        int j = mid + 1;
        help(arr, start, mid);
        help(arr, mid +1, end);
        ArrayList<Integer> aux = new ArrayList<>(end - start + 1);
        while(i <= mid && j <= end){
            if(arr.get(i) <= arr.get(j)){
                aux.add(arr.get(i));
                i++;
            }
            else{
                aux.add(arr.get(j));
                j++;
            }
        }
        while(i <= mid){
            aux.add(arr.get(i));
            i++;
        }
        while(j <= end){
            aux.add(arr.get(j));
            j++;
        }
        for(int k = 0; k < aux.size(); k++){
            arr.set(start + k, aux.get(k));
        }
    }
}