Dúvida no debug de merge sort com Javascript

Front-end
,
#1

Olá pessoal, estou estudando estruturas de dados com Javascript e até agora tava tudo ok. Só que quando eu cheguei nos algoritmos de ordenação, mais especificamente no merge sort, eu acabei travando, não consigo entender a ordem de execução que ele segue. Há uma dupla recursão, enfim, tá bem confuso pra mim. Se alguém puder ajudar eu agradeço muito. Segue o código:

var mergeSortRec = function(array) {
	var length = array.length
	
	if(length === 1) {
		return array
	}
	
	var mid = Math.floor(length / 2),
	left = array.slice(0, mid),
	right = array.slice(mid, length)
	
	return merge(mergeSortRec(left), mergeSortRec(right))
}

var merge = function(left, right) {
	var result = [],
	il = 0,
	ir = 0
	
	while(il < left.length && ir < right.length) {
		if(left[il] < right[ir]) {
			result.push(left[il++])
		} else {
			result.push(right[ir++])
		}
	}
	
	while(il < left.length) {
		result.push(left[il++])
	}
	
	while(ir < right.length) {
		result.push(right[ir++])
	}
	
	return result
}

Suponha que o array inserido seja esse: [6,2,5,2,4,5]

#2

Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas). Como o algoritmo Merge Sort usa a recursividade

Basicamente, o merge sort vai sim, dividir a estrutura do problema em partes, ordenar estas partes e, então, juntar e ordenar as partes diversas.

Veja, teu código começa dividindo a massa em 2 partes

A partir disso, você invoca o sort do lado esquerdo e do lado direito, finalizando com a junção de ambos

A ordenação é simples, porém, cada vez que a função recursiva é chamada, ela divide, novamente, a massa e vai seguindo até ter ordenado-a por completo.

1 curtida
#3

Vlw Darlan!