Merge Sort

É um algoritmo de ordenação que usa o princípio de dividir e conquistar.

Na implementação abaixo, inicialmente dividimos um vetor com N elementos em vários vetores menores. Realizadas estas divisões, teremos então vetores unitários que serão fundidos através da operação merge, formando assim vetores maiores ordenados. Isso ocorre sucessivamente até termos o vetor inteiro ordenado.


import java.io.*;
import java.util.*;
import java.lang.*;

class Main  {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int qteElementos = leitor(br);
        int[] vetor = new int[qteElementos];
       
        for (int i = 0; i < qteElementos; i++) {
            vetor[i] = leitor(br);
        }

        if (qteElementos > 1) {
            vetor = juntaVetores(vetor, 0, qteElementos);
        }
           
        imprimeVetor(vetor, qteElementos);
       
        System.exit(0);
    }

    static int[] juntaVetores(int[] vetor, int limiteInicio, int limiteFim) {
        int meio = (limiteFim+limiteInicio)/2;
       
        int qteElementos = limiteFim-limiteInicio;
        int qteElementosV1 = meio-limiteInicio;
        int qteElementosV2 = limiteFim-meio;
       
        int[] v1;
        int[] v2;
       
        if (qteElementosV1 == 1) {
            v1 = new int[1];
            v1[0] = vetor[limiteInicio];
        }
        else {
            v1 = juntaVetores(vetor, limiteInicio, meio);
        }
       
        if (qteElementosV2 == 1) {
            v2 = new int[1];
            v2[0] = vetor[meio];
        }
        else {
            v2 = juntaVetores(vetor, meio, limiteFim);
        }

        int indiceV1 = 0;
        int indiceV2 = 0;
        int indiceVetorOrdenado = 0;
               
        int[] vetorOrdenado = new int[qteElementos];
       
        while (indiceV1 < qteElementosV1 && indiceV2 < qteElementosV2) {
            if (v1[indiceV1] < v2[indiceV2]) {
                vetorOrdenado[indiceVetorOrdenado] = v1[indiceV1];
                indiceV1++;
            }
            else {
                vetorOrdenado[indiceVetorOrdenado] = v2[indiceV2];
                indiceV2++;
            }
            indiceVetorOrdenado++;
        }
       
        for (; indiceV2 < qteElementosV2; indiceV2++, indiceVetorOrdenado++) {
            vetorOrdenado[indiceVetorOrdenado] = v2[indiceV2];
        }
        for (; indiceV1 < qteElementosV1; indiceV1++, indiceVetorOrdenado++) {
            vetorOrdenado[indiceVetorOrdenado] = v1[indiceV1];
        }
       
        return vetorOrdenado;
    }
   
    static void imprimeVetor(int[] vetorOrdenado, int totalElementos) {
        for (int i = 0; i < totalElementos-1; i++) {
            System.out.print(vetorOrdenado[i] + " ");
        }
        System.out.println(vetorOrdenado[totalElementos-1]);
    }
       
    static int leitor(BufferedReader br) throws NumberFormatException, IOException {
       int n;
       int resp = 0;
       int sinal = 1;
       while (true) {
           n = br.read();
           if (n >= '0' && n <= '9') break;
           if (n == '-') sinal = -1;
           if (n == '+') sinal = 1;
       }
       while (true) {
           resp = resp*10 + n-'0';
           n = br.read();
           if (n < '0' || n > '9') break;
       }

       return resp*sinal;
    }
}