请写出自然合并排序算法： 对一个数组a，通常存在多个长度大于1的已经自然排好序的子数组段。先进行扫描，找出这些子数组段，然后进行合并。 要求：（1）写出算法思想；（2）写出算法描述（伪码）；（3）写出程序源码和执行截图。

自然合并排序（也称为插入排序）是一种简单直观的排序算法，它利用了部分有序的数据特性。算法思想主要是将大数组分割成若干小的已排序的部分，然后逐个合并这些部分直到整个数组有序。

**算法描述（伪码）：**

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

    mid = length of arr / 2
    left = mergeSort(arr[0:mid])   // 分割并递归处理左半部分
    right = mergeSort(arr[mid:])   // 同理处理右半部分

    return merge(left, right)      // 合并两个有序子数组

function merge(left, right):
    result = []
    while left and right:     // 当左右都有剩余元素时
        if left[0] <= right[0]:
            append left[0] to result
            remove first element from left
        else:
            append right[0] to result
            remove first element from right

    append remaining elements (if any) from left or right to result
    return result

**注意：** 程序源码和执行截图无法在这里提供，因为这是文本形式的交互平台，无法展示完整的程序代码或实际运行结果。你可以根据上述伪代码自行编写代码到任何支持编程语言的环境（如Python、JavaScript等）中测试。

**