自底向上合并排序算法

自底向上合并排序（Bottom-Up Merge Sort）也被称为“归并排序”的迭代版本，与传统的递归归并排序不同，它没有使用递归调用。这种算法通过不断将数组分成较小的部分，然后逐步地合并这些部分，直到整个序列有序。

基本步骤如下：

1. **分割**：从最小的子序列长度开始，比如1个元素，然后将数组分为长度为1的子数组。

2. **合并**：对于每个子数组对，比较它们的元素并将它们合并成一个有序的数组。这个过程可以逐级进行，例如，先合并长度为2的子数组，再合并长度为4的，依此类推，每次都将两个有序数组合并成更大的有序数组。

3. **重复合并**：一直持续到所有的元素都组合成一个大的有序数组为止。

这种方法避免了递归带来的栈空间开销，适用于处理大量数据或内存限制严格的场景。由于它是顺序进行的，所以常数因子比递归版本大，但总体上时间复杂度仍为O(n log n)。

以下是一个简单的自底向上合并排序的伪代码示例：

void mergeSort(vector<int>& arr, int left = 0, int right = -1) {
    if (right < 0) right = arr.size() - 1;

    // 分割阶段
    while (left < right) {
        int mid = (left + right) / 2;
        merge(arr, left, mid);
        merge(arr, mid + 1, right);
        left = mid + 1;  // 向右移动起点
    }
}

// 合并两个已排序区间
void merge(vector<int>& arr, int left, int right) {
    int n1 = right - left + 1;
    vector<int> temp(n1);
    int i = 0, j = 0, k = left;

    // 比较和合并
    while (i < n1 && j < n1) {
        if (arr[left + i] <= arr[right + j]) {
            temp[k++] = arr[left + i++];
        } else {
            temp[k++] = arr[right + j++];
        }
    }

    // 将剩余元素复制回原数组
    while (i < n1) temp[k++] = arr[left + i++]; 
    while (j < n1) temp[k++] = arr[right + j++];

    // 更新原数组
    for (i = left; i <= right; ++i) arr[i] = temp[i];
}