// O(nlogn)
// Merge two sorted arrays
const merge = (arr1, arr2) => {
	const sorted = [];
	let i = 0;
	let j = 0;

	// Loop through both arrays and push the greater elements by
	while(i < arr1.length && j < arr2.length) {
		if(arr2[j] > arr1[i]) {
			sorted.push(arr1[i]);
			i++;
		} else {
			sorted.push(arr2[j]);
			j++;
		}
	}

	// Check if there are items left in any of the arrays.
	while(i < arr1.length) {
		sorted.push(arr1[i]);
		i++;
	}
	while(j < arr2.length) {
		sorted.push(arr2[j]);
		j++;
	}

	return sorted;
}

const mergeSort = (arr) => {
	// Base case to keep splitting until there is only one item left
	if(arr.length === 1) return arr;
	// Divide array into 2 for merging
	let midIndex =  Math.floor(arr.length / 2);
	let left =  mergeSort(arr.slice(0, midIndex));
	let right = mergeSort(arr.slice(midIndex));

	// Perform merge on both side
	return merge(left, right)
}

console.log(mergeSort([33, 1, 54, 10, 2, 15])); // [ 1, 2, 10, 15, 33, 54 ]