Trade-off e Impacto

MergeSort e QuickSort resolvem o problema do custo computacional alto de algoritmos ingênuos de ordenação (como BubbleSort ou InsertionSort, que rodam em O(n^2)) ao reduzirem a complexidade média para O(n logn).

O(n logn) (Previsível)

Complexidade do MergeSort no pior caso.

O(n²) (Degradação rara)

Complexidade do QuickSort no pior caso.

O(n logn)

Complexidade média do MergeSort.

O(n logn) (Geralmente mais rápida na prática)

Complexidade média do QuickSort.

É Alto — O(n) na RAM

Uso de Memória RAM extra com MergeSort.

É Baixo — O(log n) apenas na Stack

Uso de Memória RAM extra com QuickSort.

Estável (Preserva a ordem de elementos iguais)

Estabilidade de Ordenação do MergeSort.

Não-estável (Pode alterar a ordem relativa)

Estabilidade de Ordenação do QuickSort.