// Merge two arrays
function merge(arr1, arr2) {
	var res = []
	while (arr1.length > 0 && arr2.length > 0) {
		if (arr1[0] < arr2[0]) {
			res.push(arr1.shift())
		} else {
			res.push(arr2.shift())
		}
	}
	return [...res, ...arr1, ...arr2]
}

// Recurssive Merge Sort
function mergeSort1(arr) {
	var len = arr.length
	if (len < 2) return arr
	var mid = Math.floor(len/2)
	var left = arr.slice(0, mid)
	var right = arr.slice(mid)
	return merge(mergeSort1(left), mergeSort1(right))
}

// Iterative Merge Sort
function mergeSort2(arr) {

	var result = arr.map(item => [item])

	while (result.length > 1) {
		var temp = []
		var isOddNumber = (result.length % 2 !== 0)
		for (var i = 0; i < result.length; i += 2) {
			var a = result[i]
			var b = result[i + 1]
			if (isOddNumber && i === result.length - 3) {
				b = merge(result[i + 1], result[i + 2])
				i++
			}
			temp.push(merge(a,b))
		}
		result = temp
	}
	return result[0]
}

console.log(mergeSort1([3,2,9,1,4,5]))
console.log(mergeSort2([3,2,9,1,4,5]))