编写一些伪代码来实现归并排序。
Merge Sort（A，n）
    如果 n == 1 
        返回 A 
    否则 
        将 A 拆分为两个子数组：A1 和 A2 
        a = MergeSort（A1，n/2） 
        b = MergeSort（A2，n/2） 
        返回 Merge（a，b）

Merge（A1，A2）
    创建一个空数组：A 
    i = j = 0 
    当 i < A1.length 并且 j < A2.length 时 
        如果 A1 [i] < A2 [j] 
            A.append（A1 [i]）
            i ++
        否则 
            A.append（A2 [j]）
            j ++
    将 A1 和 A2 的剩余元素添加到 A 中 
    返回 A