O paradigma divide e conquista em ciência da computação é uma técnica para dividir recursivamente problemas em subproblemas menores. Um dos aspectos principais dessa técnica é a recursão, que acontece quando uma função chama a si mesma repetidamente até que um caso base seja alcançado. Nesta lição, vamos analisar o algoritmo merge sort para entender melhor como a técnica divide e conquista funciona. Vamos supor que temos esta lista de números:

42 37 53 17

O objetivo é ordenar essa lista do menor para o maior usando o algoritmo merge sort. O primeiro passo é dividir essa lista ao meio:

42 37 | 53 17

Então precisamos olhar para o lado esquerdo da lista:

42 37

Pegamos essa sublista e dividimos ao meio novamente até que cada sublista tenha apenas um item:

42 | 37

Uma lista com apenas um item é ordenada por padrão. Em seguida, precisamos mesclar cada uma dessas sublistas de um elemento em uma lista ordenada:

37 42

Então seguimos o mesmo processo para o lado direito da lista original:

// right side of original list
53 17

// divide the list in half
53 | 17

// merge the lists in sorted order
17 53

Agora que ambas as metades da lista original estão ordenadas, nós unimos essas duas metades e ordenamos os elementos:

17 37 42 53

Aqui está como o algoritmo se parece em código:

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

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

    const sorted = [];
    let i = 0;
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            sorted.push(left[i]);
            i += 1;
        } else {
            sorted.push(right[j]);
            j += 1;
        }
    }

    return sorted.concat(left.slice(i)).concat(right.slice(j));
}

A complexidade de tempo para merge sort seria O(n log n) porque a lista é continuamente dividida ao meio (log n) e depois mesclada (O(n)). Ao contrário de outros algoritmos de ordenação como bubble sort, merge sort não é ordenado in place e tem uma complexidade de espaço de O(n).