Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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 pr, 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<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=0 e r7). Esse subarray tem ao menos dois elementos, então não é um caso base.
  • Na etapa da divisão, calculamos q=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=0 e r=3, calculamos q=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=0 e r=1, calculamos q=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 . . .
    (2 votos)
    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.