Merge Sort

O algoritmo Merge Sort é um algoritmo de classificação baseado no paradigma Divide and Conquer . Nesse algoritmo, a matriz é inicialmente dividida em duas metades iguais e, em seguida, elas são combinadas de maneira ordenada.

Processo de trabalho de classificação de mesclagem:

Pense nisso como um algoritmo recursivo que divide continuamente a matriz ao meio até que ela não possa mais ser dividida. Isso significa que se a matriz ficar vazia ou tiver apenas um elemento restante, a divisão será interrompida, ou seja, é o caso básico para interromper a recursão. Se a matriz tiver vários elementos, divida a matriz em metades e invoque recursivamente a classificação por mesclagem em cada uma das metades. Finalmente, quando ambas as metades são classificadas, a operação de mesclagem é aplicada. A operação de mesclagem é o processo de pegar duas matrizes classificadas menores e combiná-las para eventualmente criar uma maior.

Como tudo funciona

Mãos a obra:


    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Scanner;

    public class MergeSort {

        public static void main(String[] args) {
            Scanner leia = new Scanner(System.in);
            ArrayList lista = new ArrayList<>();
            int cont = 1;

            for (int i = 0; i < 1000; i++) {
                Random rand = new Random();
                int n = rand.nextInt(1000);
                lista.add(n);
            }

            MergeSort(lista, 0, lista.size() - 1);

            for (Integer integer : lista) {
                System.out.print(integer + ", ");
                if (cont % 20 == 0) {
                    System.out.println();
                }
                cont++;
            }
        }

        /* ---------------------- Algoritimo De Ordenação ---------------------- */

        public static void popula(int tot, ArrayList lista2) {
            for (int i = 0; i < tot; i++) {
                lista2.add(0);
            }
        }

        public static void MergeSort(ArrayList lista, int a, int z) {
            int m;
            if (a < z) {
                m = (a + z) / 2;
                MergeSort(lista, a, m);
                MergeSort(lista, m + 1, z);
                intercala(lista, a, m, z);
            }
        }

        public static void intercala(ArrayList lista, int a, int m, int z) {
            int poslivre, iniL1, iniL2, i;
            ArrayList lista2 = new ArrayList<>();
            popula(lista.size(), lista2);
            iniL1 = a;
            iniL2 = m + 1;
            poslivre = a;
            while (iniL1 <= m && iniL2 <= z) {
                if (lista.get(iniL1) <= lista.get(iniL2)) {
                    lista2.set(poslivre, lista.get(iniL1));
                    iniL1++;
                } else {
                    lista2.set(poslivre, lista.get(iniL2));
                    iniL2++;
                }
                poslivre++;
            }
            for (i = iniL1; i <= m; i++) {
                lista2.set(poslivre, lista.get(i));
                poslivre++;
            }
            for (i = iniL2; i <= z; i++) {
                lista2.set(poslivre, lista.get(i));
                poslivre++;
            }
            for (i = a; i <= z; i++) {
                lista.set(i, lista2.get(i));
            }
        }
    }

Tempo de execução(em segundos) VS Qtd de nº no Array:

Merge Sort	1.000	10.000	500.000	1.000.000
Bom	0.0597083	1.1589879	2103.9774235	10905.2476831
Médio	0.0263602	1.0561847	2135.3927107	10638.8583866
Ruim	0.0105934	0.8276113	2082.6098942	12852.540375

*A tabela representa a quantidade de numros utilizadas e o tempo de execução o processo de ordenação