Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CoffeeScript merge sort with tests
# 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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment