import java.util.ArrayList;

public class ImplimentationMergeSort {

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<Integer>(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));

}

}

}