Merge Sort
Última atualização
Merge sort é um algoritmo de dividir para conquistar. Ele divide recursivamente o array ao meio até que cada pedaço tenha um único elemento (que está trivialmente ordenado), e então intercala os pedaços de volta em ordem. O passo de intercalação percorre dois subarrays ordenados com dois ponteiros, sempre copiando o menor elemento da frente. Pressione reproduzir acima para ver o array ser reconstruído fusão a fusão.
Como sempre divide ao meio, o merge sort executa em tempo O(n log n) em todos os casos - seu pior caso é tão bom quanto o melhor. O custo é O(n) de espaço adicional para o buffer temporário de intercalação.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n log n) | Sempre divide a entrada ao meio |
| Caso médio | O(n log n) | Ordem aleatória |
| Pior caso | O(n log n) | Garantido - não há entradas ruins |
| Espaço | O(n) | Buffer temporário para a intercalação |
| Estável | Sim | Empates resolvidos pela esquerda durante a intercalação |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Se o intervalo tem 0 ou 1 elementos, já está ordenado. |
| 2 | Divide o intervalo em duas metades. |
| 3 | Ordena recursivamente a metade esquerda com merge sort. |
| 4 | Ordena recursivamente a metade direita com merge sort. |
| 5 | Intercala as duas metades ordenadas com dois ponteiros. |
Exemplo resolvido
Ordenando [5, 2, 4, 1]:
| Passada | Array | Ação |
|---|---|---|
| Dividir | [5, 2] | [4, 1] | Divide o array em duas metades |
| Dividir | [5] [2] | [4] [1] | Divide de novo até que cada pedaço seja um único elemento |
| Intercalar | [2, 5] | [1, 4] | Intercala [5],[2] em [2, 5] e [4],[1] em [1, 4] |
| Intercalar | [1, 2, 4, 5] | Intercala [2, 5] e [1, 4]: escolhe 1, depois 2, depois 4, depois 5 |
| Pronto | [1, 2, 4, 5] | O array está totalmente ordenado |
Quando usar o merge sort
| Use quando | Evite quando |
|---|---|
Você precisa de um pior caso garantido de O(n log n) | A memória é limitada e O(n) de espaço extra é inaceitável |
| A estabilidade importa (chaves iguais mantêm sua ordem) | Você ordena arrays pequenos onde o insertion sort é mais rápido |
| Você ordena uma lista encadeada | A ordenação in-place é um requisito rígido |
| Os dados são grandes demais para a RAM (ordenação externa) | A localidade de cache domina e as passadas in-place do quicksort vencem |
Código de Merge Sort
Uma implementação limpa e executável de Merge Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Merge Sort em Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Código de Merge Sort em JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Código de Merge Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Código de Merge Sort em C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Código de Merge Sort em C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}Perguntas frequentes sobre Merge Sort
Qual é a complexidade de tempo do merge sort?
Merge sort é
O(n log n) no melhor, no médio e no pior caso, porque sempre divide o array ao meio. Ele usa O(n) de espaço adicional para o buffer de intercalação.O merge sort é estável?
Sim, quando o passo de intercalação resolve os empates pegando primeiro da metade esquerda. Isso mantém os elementos iguais em sua ordem relativa original, por isso o merge sort é uma escolha comum para ordenação estável.
Por que usar merge sort em vez de quicksort?
Merge sort garante
O(n log n) mesmo em entradas adversas e é estável, enquanto o quicksort pode degradar para O(n²). Merge sort também é preferido para listas encadeadas e ordenação externa. A desvantagem é sua memória adicional de O(n).Qual é a diferença entre merge sort e quicksort?
Ambos são ordenações de dividir para conquistar, mas o quicksort particiona em torno de um pivô e ordena in-place com
O(log n) de espaço de pilha, enquanto o merge sort divide cegamente ao meio e intercala usando um buffer de O(n). Quicksort costuma ser mais rápido na prática por causa da localidade de cache, mas o merge sort tem um pior caso garantido de O(n log n) e é estável.Quando devo usar merge sort na prática?
Recorra ao merge sort quando precisar de uma ordenação estável com limite garantido de
O(n log n), ao ordenar listas encadeadas (onde não precisa de acesso aleatório), ou ao fazer ordenação externa de dados grandes demais para caber na memória. Evite-o quando a memória é escassa, pois ele precisa de O(n) de espaço adicional.O merge sort ordena in-place?
Não. O merge sort padrão aloca um buffer temporário de
O(n) para intercalar as duas metades, então não é in-place. Existem variantes de intercalação in-place, mas são complexas e ou mais lentas ou perdem a estabilidade, então a versão baseada em buffer é a escolha comum.Recursos relacionados
Mais visualizações
