归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法，它的基本思路是将一个大的数组拆分成若干个小的数组，对每个小的数组进行排序，最后将这些小的数组合并成一个有序的数组。具体实现时，可以使用递归或迭代的方式来完成。

归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)，它是一种稳定的排序算法，适用于任何数据类型的排序。但是，归并排序需要额外的空间来存储临时数组，因此在数据量比较大的情况下，可能会带来一定的空间开销。

以下是归并排序的基本步骤：

1. 分治：将待排序的数组拆分成两个子数组，分别对这两个子数组进行排序。

2. 合并：将两个已经排好序的子数组合并成一个有序的数组。

3. 重复：重复以上两个步骤，直到所有的子数组都被排序完成。

下面是归并排序的递归实现的伪代码：

mergeSort(array, left, right)
    if left < right
        middle = (left + right) / 2
        mergeSort(array, left, middle)
        mergeSort(array, middle + 1, right)
        merge(array, left, middle, right)

其中，`array`是待排序的数组，`left`和`right`是数组的左右下标界限，`middle`是数组中间元素的下标。

`merge()`函数的作用是将两个已经排好序的子数组合并成一个有序的数组。以下是`merge()`函数的伪代码：

merge(array, left, middle, right)
    n1 = middle - left + 1
    n2 = right - middle
    leftArray[1...n1+1] = array[left...middle]
    rightArray[1...n2+1] = array[middle+1...right]
    leftArray[n1+1] = INFINITY
    rightArray[n2+1] = INFINITY
    i = 1, j = 1
    for k = left to right
        if leftArray[i] <= rightArray[j]
            array[k] = leftArray[i]
            i = i + 1
        else
            array[k] = rightArray[j]
            j = j + 1

其中，`n1`和`n2`是左右子数组的长度，`leftArray`和`rightArray`是临时数组，`INFINITY`是一个无穷大的数，确保当左子数组或右子数组已经被遍历完时，可以将另一个子数组的剩余部分直接拷贝到原数组中。最后，使用`for`循环将左右子数组中的元素按照大小顺序合并到原数组中。