算法001

归并排序是分而治之的典型用法，其实现大致有4个步骤
    1： 如果排序列表的长度为0或1，说明已经排序，直接返回。
    2：把未排序列表从中间分为2个列表
    3：递归的排序2个子列表
    4：合并这2个子列表
归并排序的优点：
   1：在小列表上排序所需的步骤元少于大列表排序的步骤
   2：从2个有序的列表中构建有序列表所需步骤远少于未排序的2个的合并步骤

function mergesort(m)
    var list left, right, result
    if length(m) ≤ 1
        return m

    var middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = mergesort(left)
    right = mergesort(right)
    result = merge(left, right)
    return result


function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    if length(left) > 0
        append rest(left) to result
    if length(right) > 0
        append rest(right) to result
    return result