写出归并排序的伪代码

归并排序是一种分治算法，它的基本思想是将一个大的问题分解为两个较小的子问题，然后递归地解决这些子问题，最后合并它们的解来得到原问题的解。下面是归并排序的伪代码：

function mergeSort(array):
    if length(array) <= 1:  // 如果数组只有一个元素或为空，直接返回
        return array

    // 将数组分为两半
    mid = length(array) / 2
    leftHalf = mergeSort(array[0:mid])
    rightHalf = mergeSort(array[mid:length(array)])

    // 合并两个有序子数组
    return merge(leftHalf, rightHalf)

function merge(leftArray, rightArray):
    result = empty list  // 创建一个空列表来存放结果
    while leftArray and rightArray:  // 只要两边都有元素
        if leftArray <= rightArray:  // 选择左边的元素先放入结果
            append leftArray to result
            remove first element from leftArray
        else:  // 否则选择右边的元素
            append rightArray[0] to result
            remove first element from rightArray

    # 将剩余的元素（如果有）添加到结果中
    while leftArray:  // 左边还有元素，直接添加
        append leftArray[0] to result
        remove first element from leftArray
    while rightArray:  -- 右边还有元素，直接添加
        append rightArray to result
        remove first element from rightArray

    return result