自然合并排序算法伪码

自然合并排序是一种基于分治策略的排序算法，它将待排序序列分为两个子序列，分别对它们进行排序，然后合并已排序的部分。以下是合并排序的伪代码：

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

    middle = length(array) / 2  // 计算中间索引
    left = mergeSort(array[0:middle])  // 对左半部分递归排序
    right = mergeSort(array[middle:])   // 对右半部分递归排序

    return merge(left, right)           // 合并两个已排序的部分

function merge(left, right):     // 合并两个有序数组
    result = []
    while left and right:         // 当左右都有元素时继续循环
        if left[0] <= right[0]:   // 如果左元素较小，添加到结果并移动指针
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    # 如果其中一个数组还有剩余，将其余所有元素添加到结果
    result.extend(left if left else right)
    return result