Merge Sort

by Anton Bagayev

JavaScript

function mergeSort(array) {
	if (array.length == 1) {
		return array;
	} else {
		let midIndex = Math.floor(array.length / 2);
		let firstHalf = array.slice(0, midIndex);
		let secondHalf = array.slice(midIndex);

		return merge(mergeSort(firstHalf), mergeSort(secondHalf));
	}
}

function merge(firstHalf, secondHalf) {
	let firstIndex = 0;
	let secondIndex = 0;
	let result = [];
	
	while((firstIndex < firstHalf.length) && (secondIndex < secondHalf.length)) {
		if (firstHalf[firstIndex] < secondHalf[secondIndex]) {
			result.push(firstHalf[firstIndex]);
			firstIndex++;
		} else {
			result.push(secondHalf[secondIndex]);
			secondIndex++;
		}
	}
	while(firstIndex < firstHalf.length) {
		result.push(firstHalf[firstIndex]);
		firstIndex++;
	}
	while(secondIndex < secondHalf.length) {
		result.push(secondHalf[secondIndex]);
		secondIndex++;
	}
	
	return result;
}


console.log(mergeSort([13, 9, 123, 25, 40, 10, 9, 25]));