Oi Lucas, em geral estamos interessados no pior caso quando analisamos o custo de um algoritmo. O melhor caso não diz muito quão eficiênte um algoritmo pode ser para entradas arbitrárias. No caso particular do MergeSort, o pior e melhor caso tem o mesmo custo computacional, mas nem sempre é assim. Recomendo o seguinte video em que falamos mais sobre o assunto: ruclips.net/video/k7MBTnDfQxA/видео.html Um abraço!
Tenho uma duvida sobre a divisão, exemplo o lado esquerdo nivel 0, quando o novo subvetor 1 e criado na pilha ele tem as posições do início ate a metade do vetor nivel 0, a outra metade do vetor nivel 0 que fico do lado direito ela fica separada na pilha no mesmo nivel do subvetor 1?
Basicamente é isso mesmo, no entanto, observe que o subvetores não são criados (apenas os apontadores), essa parte é feita in-place (diretamente no vetor v). Diferente da função merge, que de fato aloca um vetor aux para guardar o resultado da intercalação. Até mais!
![[C] 113. Quick Sort](http://i.ytimg.com/vi/oSQ2hSJLRU4/mqdefault.jpg)
![[C] 113. Quick Sort](/img/tr.png)
Olá, professor, boa noite. A minha curiosidade é: eu queria saber o porquê da nuance do melhor caso e o do pior caso. O que difere entre os dois.
Oi Lucas, em geral estamos interessados no pior caso quando analisamos o custo de um algoritmo. O melhor caso não diz muito quão eficiênte um algoritmo pode ser para entradas arbitrárias. No caso particular do MergeSort, o pior e melhor caso tem o mesmo custo computacional, mas nem sempre é assim. Recomendo o seguinte video em que falamos mais sobre o assunto: ruclips.net/video/k7MBTnDfQxA/видео.html
Um abraço!
Tenho uma duvida sobre a divisão, exemplo o lado esquerdo nivel 0, quando o novo subvetor 1 e criado na pilha ele tem as posições do início ate a metade do vetor nivel 0, a outra metade do vetor nivel 0 que fico do lado direito ela fica separada na pilha no mesmo nivel do subvetor 1?
Basicamente é isso mesmo, no entanto, observe que o subvetores não são criados (apenas os apontadores), essa parte é feita in-place (diretamente no vetor v). Diferente da função merge, que de fato aloca um vetor aux para guardar o resultado da intercalação.
Até mais!