Merge Sort

Last updated Aug 6, 2023 Edit Source

• Programming
• Interviewprep
• Algorithms
• Sorting

Es un algoritmo de sorting en el cual una estructura de datos es dividida a su unidad mas minima (1) para posteriormente ser unidas (mergidas) la una con la otra de forma que vayan siendo ordenadas a la vez. Este algoritmo suele implementar la Recursividad.

In merge sort, the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order.

Pseudocodigo:

1
2
3
4
5
6

if arrayLength <= 1 // Caso Base
	return [array]
else  // Caso Recursivo
	Sort left half of the array
	Sort right half of the array
	Merge two halves together

Complejidad: Worst-case scenario: O(n log n) best-case scenario: Omega(n log n)

Siguiente: