CodeUtility
Tornando o seu trabalho de dev mais simples!
Algoritmos C/C++

Ordenação por intercalação (merge sort) em C e C++

Nesta lição, você vai implementar o merge sort com a estratégia de dividir para conquistar, que sempre roda em O(n log n).

Introdução

O merge sort divide o array em duas metades, ordena cada uma com chamadas recursivas e depois intercala as duas metades ordenadas em uma sequência ordenada. A grande vantagem é que o tempo de execução é sempre O(n log n), não importa como os dados chegam.

Pontos importantes

  • Teste com entradas vazias, com um único elemento, com valores repetidos e já ordenadas.
  • Primeiro faça funcionar corretamente, depois otimize.
  • Em código real, prefira as funções prontas da biblioteca padrão.

Visualizador de Ordenação por intercalação (merge sort) em C e C++

O(n)

Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.

Exemplos de código C e C++

C
Executar →
main.c
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}
Resultado da execução
2 3 6 7 8
C++
Executar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Resultado da execução
2 3 6 7 8

Comparação entre C e C++

A função merge_sort em C para quando o trecho tem menos de 2 elementos. Depois de ordenar as duas metades, o laço while escolhe o menor elemento do início de cada metade e o copia para o array temporário temporary, e em seguida copia o que sobrou. As duas versões precisam de O(n) de memória extra. A versão em C gerencia o array temporário à mão, e a versão em C++ usa vector e algoritmos padrão para deixar o código mais claro.

C

Laços, ponteiros, tamanhos e buffers temporários são escritos explicitamente.

C++

Iteradores e algoritmos padrão separam o processamento da forma como os dados são guardados.

Exercícios práticos

Execute as duas versões e depois mude o código para observar a diferença de segurança que cada linguagem oferece.

  • Simule cada comparação no papel.
  • Teste com valores repetidos e com valores muito grandes e muito pequenos.
  • Meça o tempo do seu código e compare com a biblioteca padrão.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios