Merge Sort

function sort(arr){
	if(arr.length < 2){
		return arr;
	}

	let length = arr.length;
	let halfNumber = Math.floor(length / 2);
	let left = arr.slice(0, halfNumber);
	let right = arr.slice(halfNumber);

	return merge(sort(left), sort(right))
	
}

function merge(left, right){
	let result = [];
	let i = 0;
	let j = 0;

	while(left[i] !== undefined || right[j] !== undefined){
		if(right[j] == undefined || right[j] > left[i]){
			result.push(left[i]);
			i++;
		} else {
			result.push(right[j]);
			j++;
		}
	}

	return result;
}


sort([2,6, 78, 86,34,56, 15, 90, 9, 25, 0, 64])
/*

[4,1,3,2] --> [4, 1] [3, 2] --> [4] [1]  [3] [2]

sort([4,1,3,2]) --> merge(sort([4, 1]), sort([3, 2])) --> merge(merge(sort([4]), sort([1])),merge(sort([3]), sort([2])))

merge(merge([4], [1]), merge([3], [2])) --> merge([1, 4], [2, 3]) --> [1, 2, 3, 4]

*/