SHARE
TWEET

MergeSort

a guest Apr 26th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package Sort;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class MergeSort {
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.         int[] arr = new int[in.nextInt()];
  9.         for (int i = 0; i < arr.length; i++) {
  10.             arr[i] = in.nextInt();
  11.         }
  12.         mergeSort(arr, 0, arr.length - 1);
  13.         for (int i = 0; i < arr.length; ++i) {
  14.             System.out.print(arr[i] + " ");
  15.         }
  16.         System.out.println();
  17.     }
  18.  
  19.     static void mergeSort(int arr[], int l, int r) {
  20.         if (l < r) {
  21.             int m = (l + r) / 2;
  22.  
  23.             //Divide até chegar nos átomos.
  24.             mergeSort(arr, l, m);
  25.             mergeSort(arr, m + 1, r);
  26.             //Vai retornando ordenando os átomos em parcelas maiores.
  27.             merge(arr, l, m, r);
  28.         }
  29.     }
  30.  
  31.     static void merge(int arr[], int l, int m, int r) {
  32.         //Define o tamanho dos arrays temporários.
  33.         int size1 = m - l + 1;
  34.         int size2 = r - m;
  35.         //Cria os dois arrays temporários.
  36.         int[] L = new int[size1];
  37.         int[] R = new int[size2];
  38.         //Preenche os dois arrays temporários.
  39.         for (int i = 0; i < size1; i++) {
  40.             L[i] = arr[l + i];
  41.         }
  42.         for (int i = 0; i < size2; i++) {
  43.             R[i] = arr[m + i + 1];
  44.         }
  45.         /*
  46.         Seta o local de começo de todas as partes a serem percorridas.
  47.         (arrays temporarios e array principal sendo montado)
  48.         */
  49.         int i = 0, j = 0;
  50.         int k = l;
  51.         /*
  52.         Vai preenchendo o array principal, comparando os dois arrays temporários
  53.         de acordo com a posição corrente do teste. Para economizar espaço de teste,
  54.         após terminar de percorrer um dos arrays temporários, ele preenche com o que
  55.         restar do outro.
  56.         */
  57.         while (i < size1 && j < size2) {
  58.             if (L[i] <= R[j]) {
  59.                 arr[k] = L[i];
  60.                 i++;
  61.             } else {
  62.                 arr[k] = R[j];
  63.                 j++;
  64.             }
  65.             k++;
  66.         }
  67.         //Preenche com o que restar.
  68.         while (i < size1) {
  69.             arr[k] = L[i];
  70.             i++;
  71.             k++;
  72.         }
  73.         while (j < size2) {
  74.             arr[k] = R[j];
  75.             j++;
  76.             k++;
  77.         }
  78.     }
  79. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top