If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Visão geral do merge sort

Como estamos usando divisão e conquista para ordenar, precisamos decidir quais serão nossos subproblemas. O problema completo é ordenar um array inteiro. Vamos dizer que um subproblema é ordenar um subarray. Em particular, iremos pensar em um subproblema como ordenar o subarray começando de um índice p e continuamos através do índice r. Isso será conveniente para termos uma notação para um subarray, então vamos dizer que array[p..r] denota o subarray de array. Note que estes "dois pontos" não são aceitos em JavaScript; estamos usando apenas para descrever o algoritmo, ao invés de uma implementação particular de um algoritmo em código. Nós termos nossa notação, para um array de n elementos, podemos dizer que o problema original é ordenar o array[0..n-1].
Veja abaixo como o merge sort usa divisão e conquista:
  1. Divisão pelo número encontrado q para a posição entre p e r. Faça isso da mesma forma que encontramos o ponto médio na busca binária: adicione p e r, divida por 2, e arredonde para baixo.
  2. Conquiste organizando recursivamente os subarrays em cada dois subproblemas criados pela etapa da divisão. Isso é, organize recursivamente o subarray array[p..q] e organize recursivamente o subarray array[q+1..r].
  3. Combine juntando os dois subarrays oganizados de volta em um único subarray array[p..r] organizado.
Precisamos de um caso base. O caso base é um subarray contendo menos do que dois elementos, isto é, quando p, is greater than or equal to, r, uma vez que um subarray sem elementos ou com apenas um elemento já está ordenado. Então iremos dividir, conquistar e combinar apenas quando p, is less than, r.
Vamos ver um exemplo. Começaremos com um array contendo [14, 7, 3, 12, 9, 11, 6, 2], então o primeiro subarray é na verdade o array completo, array[0..7](p, equals, 0 e r, minus, 7). Esse subarray tem ao menos dois elementos, então não é um caso base.
  • Na etapa da divisão, calculamos q, equals, 3.
  • Na etapa da conquista ordenamos dois subarrays array[0..3], o qual contém [14, 7, 3, 12], e array[4..7], o qual contém [9, 11, 6, 2]. Quando voltamos a etapa da conquista, cada um dos dois subarrays estão ordenados: array[0..3] contém [3, 7, 12, 14] e array[4..7] contém [2, 6, 9, 11], então o array completo é [3, 7, 12, 14, 2, 6, 9, 11].
  • Finalmente, a etapa de combinação junta os dois subarrays ordenados na primeira e na segunda metade, produzindo o array final ordenado: array [2, 3, 6, 7, 9, 11, 12, 14].
Como o subarray array[0..3] ficou ordenado? Do mesmo modo. Existe mais do que dois elementos, então este não é um caso base. Com p, equals, 0 e r, equals, 3, calculamos q, equals, 1, ordenamos recursivamente o array[0..1] ([14, 7]) e o array[2..3] ([3, 12]), resultando no array[0..3] contendo [7, 14, 3, 12], e juntamos a primeira metade com a segunda metade, produzindo [3, 7, 12, 14].
Como o subarray array[0..1] tornou-se ordenado? Com p, equals, 0 e r, equals, 1, calculamos q, equals, 0, ordenamos recursivamente o array[0..0] ([14]) e o array[1..1] ([7]), resultando no array[0..1] ainda contendo [14, 7], e juntamos a primeira metade com a segunda metade, produzindo [7, 14].
Os subarrays array[0..0] e array[1..1] são casos base, dado que contém menos do que dois elementos. É assim que o algoritmo merge sort completo se desenrola:
A maioria das etapas no merge sort são simples. Você pode verificar facilmente o caso base. Encontrar o ponto médio q na etapa da divisão também é muito fácil. Você precisa fazer duas chamadas recursivas na etapa da conquista. É na etapa da combinação, em que você precisa juntar dois subarrays ordenados, que o trabalho real acontece.
No próximo desafio, você vai se concentrar em implementar o algoritmo merge sort completo, para ter certeza que você entendeu como dividir e conquistar recursivamente. Depois de fazer isso, vamos nos aprofundar em como juntar dois subarrays ordenados eficientemente e você vai implementar isso em um desafio mais adiante.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

  • Avatar duskpin seedling style do usuário jspionbh
    ola queria implementar o mergesort em uma arquivo ordenando os seus nº registros .tipo uma arquivo csv com 3 campos e nº registros.


    ordem ano I uf I valor
    12 I 1975 I mg I 0,98888

    23 . . .
    18 . . .
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.