CoffeeScript merge sort with tests

mergesort.coffee

# Non-destructive merge sort.
# [1, 8, 12, 5].mergeSort()
Array::mergeSort = ->

	# If the array has one element, we're done.
	return this if @length is 1

	# Split the array in half.
	halfwayMark = Math.floor(@length / 2)
	firstHalf = @slice(0, halfwayMark)
	secondHalf = @slice(halfwayMark)

	# Sort the halves.
	firstHalf = firstHalf.mergeSort()
	secondHalf = secondHalf.mergeSort()

	# Construct the result from that.
	result = []
	while firstHalf.length or secondHalf.length
		if firstHalf.length and secondHalf.length
			if firstHalf[0] <= secondHalf[0]
				result.push firstHalf.shift()
			else
				result.push secondHalf.shift()
		else if firstHalf.length
			result.push firstHalf.shift()
		else if secondHalf.length
			result.push secondHalf.shift()

	# All done!
	return result

########################################################################

# Test setup
assert = console.assert
eq = (a, b) ->
	return false if a.length isnt b.length
	for num, i in a
		return false if num != b[i]
	return true

# Tests
assert eq([0].mergeSort(), [0])
assert eq([1].mergeSort(), [1])
assert eq([1, 2].mergeSort(), [1, 2])
assert eq([2, 1].mergeSort(), [1, 2])
assert eq([1, 2, 3].mergeSort(), [1, 2, 3])
assert eq([2, 1, 3].mergeSort(), [1, 2, 3])
assert eq([3, 1, 2].mergeSort(), [1, 2, 3])
assert eq([3, 2, 1].mergeSort(), [1, 2, 3])
assert eq([0, 2, 3].mergeSort(), [0, 2, 3])
assert eq([2, 0, 3].mergeSort(), [0, 2, 3])
assert eq([3, 0, 2].mergeSort(), [0, 2, 3])
assert eq([3, 2, 0].mergeSort(), [0, 2, 3])
assert eq([4,3,9,25,25,0,-19,55,43].mergeSort(), [-19,0,3,4,9,25,25,43,55])