Atividade Extra - Algoritmo Merge Sort

MergeSort.java

package Mergesort;
import java.util.Arrays;

public class Merge {
    
    public void merge(int arr[], int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;

        int L[] = new int[n1];
        int M[] = new int[n2];

        for (int i = 0; i < n1; i++){
            L[i] = arr[p + i];
        }
            
        for (int j = 0; j < n2; j++){
            M[j] = arr[q + 1 + j];
        }

        int i, j, k;
        i = 0;
        j = 0;
        k = p;

        while (i < n1 && j < n2) {
            if (L[i] <= M[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = M[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = M[j];
            j++;
            k++;
        }
    }

    public void Sort(int arr[], int l, int r) {
        if (l < r) {
            // Divisão do vetor
            int m = (l + r) / 2;

            Sort(arr, l, m);
            Sort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }
  
    public static void main(String args []){
        Merge merge = new Merge();
        
        int[] vetor = {78, 52, 36, 17, 15, 10, 22, 41, 67};
        //int[] vetor = {50,30,40,80,10,20,70,60};
        int tamanho = vetor.length;
        
        System.out.println("MERGE SORT:");
        System.out.println("Tamanho do Array: " + tamanho);
        System.out.println("Vetor Original: " + Arrays.toString(vetor));        

        merge.Sort(vetor, 0, tamanho - 1);
        System.out.println("\nVetor Ordenado: " + Arrays.toString(vetor));
    }
}