合并排序

merge_sort.coffee

merge = (left, right)->
    i = j = 0
    arr =[]
    while i < left.length || j < right.length
        if i is left.length
            arr = arr.concat right.slice j, right.length
            break
        if j is right.length
            arr = arr.concat left.slice i, right.length
            break
        if left[i] < right[j]
            arr.push left[i++]
        else
            arr.push right[j++]
    arr
merge_sort = (arr)->
    return arr if arr.length <= 1
    mid = arr.length / 2
    mid = parseInt mid
    left = arr.slice 0 , mid
    right = arr.slice mid, arr.length
    merge merge_sort(left), merge_sort(right)

# test
console.log merge_sort []
console.log merge_sort [1]
console.log merge_sort [1,2]
console.log merge_sort [2,1]
console.log merge_sort [1,1]
console.log merge_sort [1,5,3,6,7]
console.log merge_sort [1,5,3,6,7,1,5,3,6,7,1,5,3,6,7,1,5,3,6,7]