MergeSort.js

/*
 * original version can be found in:
 * https://gist.github.com/paullewis/1982121
 * sort(some-random-array) will return sorted array
 */
const merge = (left, right) => {

	const result = []
	
	while(left.length && right.length) {
		if (left[0] < right[0]) {
			result.push(left.shift())
		} else if (left[0] > right[0]){
			result.push(right.shift())
		} else {
			result.push(left.shift())
			result.push(right.shift())
		}
	}

	if (left.length) {
		return result.concat(left)
	}
	return result.concat(right)
}

const sort = (array) => {
	const mid = Math.floor(array.length / 2)
	const left = array.slice(0, mid)
	const right = array.slice(mid)

	if (array.length === 1) {
	    	return array
	}

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