fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. void merge(int *arr, int lo, int m, int hi) {
  4.     int n1 = m - lo + 1; //maximo do subarray1
  5.     int n2 = hi - m; //maximo do subarray2
  6.     int *L = (int*)malloc(sizeof(int) * n1);
  7.     int *R = (int*)malloc(sizeof(int) * n2);
  8.     for (int i = lo; i < n1; i++) {
  9.         L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray 
  10.     } //obs: vai de lo ateh n1-1
  11.     for (int j = hi; j < n2; j++) {
  12.         R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
  13.     }// obs vai de m+1 ateh n2-1
  14.     int i = 0;
  15.     int j = 0;
  16.     int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
  17.     while (i < n1 && j < n2) {
  18.         if (L[i] <= R[j]) {
  19.             arr[k] = L[i]; //se o de L for menor, arr recebe de L
  20.             i++;
  21.         } else {
  22.             arr[k] = R[j++]; //se o de R for menor, arr recebe de R
  23.         }
  24.         k++; //vai preenchendo arr[k]
  25.     }
  26.     while (i<n1){ // termina de preencher arr com o q falta de L
  27.         arr[k++] = L[i++];
  28.     }
  29.     while (j < n2) { // termina de preencher arr com o q falta de R
  30.         arr[k++] = R[j++];
  31.     }
  32. }
  33. void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
  34.     if (lo < hi) {
  35.         int m = (hi + lo) / 2;
  36.         mergesort(arr, lo, m);
  37.         mergesort(arr, m + 1, hi);
  38.         merge(arr, lo, m, hi);
  39.     }
  40. }
  41. void printarr(int *arr, size_t size){ //imprime array ordenado
  42.     for (int i = 0; i < size; i++){
  43.         cout << arr[i] << " ";
  44.     }
  45. }
  46. int main() {
  47. 	int N;
  48. 	cin >> N;
  49. 	int *vetor = (int *)malloc(sizeof(int) * N);
  50. 	for (int i = 0; i < N; i++) {
  51. 	    cin >> vetor[i];
  52. 	}
  53. 	mergesort(vetor, 0, N);
  54. 	printarr(vetor, N);
  55. }
  56.  
  57. //https://pt.stackoverflow.com/q/189421/101
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
7
5
3
6
4
8
2
1
stdout
copy 
0 0 0 0 0 0 0
https://ideone.com/Qv9HfQ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!