merge-sort.js

function merge(left, right) { // Recebe 1 array referente a metade da esquerda do array original e 1 array referente a metade da direita.
    let resultArray = [] // Array que retornaremos ordenado
    let leftIndex = 0 // índice inicial do subarray esquerdo
    let rightIndex = 0; // índice inicial do subarray direito

    while (leftIndex < left.length && rightIndex < right.length) { // Rodamos um loop enquanto o índice do subarray esquerdo e o índice do subarray direito for menor que o tamanho dos seus respectivos subarrays.
        if(left[leftIndex] < right[rightIndex]) { // Se o elemento do subarray esquerdo no índice definido for menor que o elemento do subarray direito no índice definido
            resultArray.push(left[leftIndex]); // Adicionamos o elemento esquerdo no array e incrementamos o índice esquerdo para seguir pro próximo valor.
            leftIndex++;
        } else { // Senão, adicionamos o elemento direito no array de resultado e incrementamos o índice direito para seguir pro próximo valor.
            resultArray.push(right[rightIndex]);
            rightIndex++;
        }
    }
    

    //Quando o loop acaba, é possível que um dos arrays ainda tenha elementos sobrando (o outro que "ganhou" todas as comparações). Como esses elementos restantes já estão ordenados entre si e são todos maiores que o que já está em resultArray, basta colar (concat) o que sobrou de left e de right no final — só um dos dois slice vai realmente ter conteúdo, o outro será um array vazio.

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


function mergeSort(array) { // Recebe o array não ordenado
    if(array.length <= 1) { // Caso Base: Se o tamanho do array for igual ou menor que 1, por definição ele já está ordenado, então retornamos ele 
        return array;
    }

    const middle = Math.floor(array.length / 2) // pegamos o índice da metade do array arredondando para baixo para evitar números flutuantes.
    const left = array.slice(0, middle); // Definimos a metade esquerdo sendo do primeiro valor do array original até o meio
    const right = array.slice(middle); // Definimos a metade direita sendo do meio do array original até o último valor.

    return merge( // Chamamos a função de unir os elementos na ordem passando a função de cortar os elementos pela metade recursivamente
        mergeSort(left), // Passamos a metade esquerda para ser divida ao meio
        mergeSort(right) // Passamos a metade direita para ser divida ao meio
    )

    // Ao finalizar toda as execuções da Call Stack e sobrar subarrays com apenas 1 valor, a função de merge é invocada

}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));