MergeSort

package Sort;

import java.util.Scanner;

public class MergeSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] arr = new int[in.nextInt()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        mergeSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    static void mergeSort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;

            //Divide até chegar nos átomos.
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            //Vai retornando ordenando os átomos em parcelas maiores.
            merge(arr, l, m, r);
        }
    }

    static void merge(int arr[], int l, int m, int r) {
        //Define o tamanho dos arrays temporários.
        int size1 = m - l + 1;
        int size2 = r - m;
        //Cria os dois arrays temporários.
        int[] L = new int[size1];
        int[] R = new int[size2];
        //Preenche os dois arrays temporários.
        for (int i = 0; i < size1; i++) {
            L[i] = arr[l + i];
        }
        for (int i = 0; i < size2; i++) {
            R[i] = arr[m + i + 1];
        }
        /*
        Seta o local de começo de todas as partes a serem percorridas.
        (arrays temporarios e array principal sendo montado)
        */
        int i = 0, j = 0;
        int k = l;
        /*
        Vai preenchendo o array principal, comparando os dois arrays temporários
        de acordo com a posição corrente do teste. Para economizar espaço de teste,
        após terminar de percorrer um dos arrays temporários, ele preenche com o que
        restar do outro.
        */
        while (i < size1 && j < size2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        //Preenche com o que restar.
        while (i < size1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < size2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}