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:

Precisamos de um caso base. O caso base é um subarray contendo menos do que dois elementos, isto é, quando $p\ge 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<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 $r-7$‍). Esse subarray tem ao menos dois elementos, então não é um caso base.

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.