Skip to main content

Merge Sort

O Merge Sort é um algoritmo de ordenação eficiente que utiliza a técnica de dividir e conquistar. Ele divide o array em duas metades, ordena cada metade recursivamente e depois combina as duas metades ordenadas.

Complexidade​

  • Tempo: O(n log n)
  • Espaço: O(n)

Implementação​

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Exemplo de Uso​

const array = [38, 27, 43, 3, 9, 82, 10];
console.log('Array original:', array);

const sortedArray = mergeSort(array);
console.log('Array ordenado:', sortedArray);
// Saída: Array ordenado: [3, 9, 10, 27, 38, 43, 82]

Quando Usar​

  • Quando você precisa de um algoritmo de ordenação estável
  • Quando a complexidade de tempo garantida O(n log n) é importante
  • Quando você tem memória suficiente disponível
  • Em grandes conjuntos de dados onde a eficiência é crucial

Vantagens e Desvantagens​

Vantagens​

  • Tempo de execução garantido O(n log n)
  • Estável (mantém a ordem relativa de elementos iguais)
  • Bom para ordenar linked lists

Desvantagens​

  • Requer espaço adicional O(n)
  • Para arrays pequenos, pode ser mais lento que algoritmos mais simples
  • Complexidade de implementação maior que algoritmos básicos