给定一个大小为 n 的数组，我们的任务是使用迭代归并排序对给定数组进行排序。
示例：
> 输入： arr[] = [4, 1, 3, 9, 7]
> 输出： [1, 3, 4, 7, 9]
> 解释： 输出数组已排序。
>
> 输入： arr[] = [1, 3 , 2]
> 输出： [1, 2, 3]
> 解释： 输出数组已排序。
关于典型的递归解法，请参阅 归并排序。
方法：
> 核心思路是实现一种避免递归的迭代归并排序。我们采用自底向上的方法，从单个元素开始，逐步合并尺寸递增（1, 2, 4, 8…）的已排序子数组。在每一层中，我们将相邻的子数组配对并合并，直到整个数组排序完成。
详细解释：
- 在传统的递归归并排序中，我们采用自顶向下的方法，不断地将数组一分为二，直到只剩下单个元素。然而，这种方法需要维护函数调用栈，并且涉及函数调用的开销。
- 迭代版本通过自底向上的工作方式消除了这种开销。我们首先将每个元素视为一个大小为 1 的已排序子数组。然后在每一轮遍历中，我们合并这些已排序子数组的相邻对，以形成更大的已排序子数组。
- 外层循环控制正在合并的子数组的大小，该大小在每次迭代中翻倍（1, 2, 4, 8…）。对于每个大小，我们遍历数组以找到要合并的相邻子数组对。
- 一个关键点在于处理大小不是 2 的幂的数组。例如，对于 7 个元素，当合并大小为 2 的子数组时，我们可能会遇到像 (2, 2, 2, 1) 这样的组合。算法通过使用 min 函数来正确计算子数组的端点，从而优雅地处理这种情况。
C++
CODEBLOCK_b6aacfa0
Java
// Java program to perform
// iterative merge sort.
import java.util.*;
class GfG {
// Helper function to merge two sorted portions of the array
static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid – left + 1;
int n2 = right – mid;
// Create temporary arrays
// for left and right subarrays
int[] arr1 = new int[n1], arr2 = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
arr1[i] = arr[left + i];
for (int j = 0; j < n2; j++)
arr2[j] = arr[mid + 1 + j];
int i = 0;
int j = 0;
int k = left;
// Merge the temp arrays back into arr
while (i < n1 && j < n2) {
if (arr1[i] <= arr2[j]) {
arr[k] = arr1[i];
i++;
} else {
arr[k] = arr2[j];
j++;
}
k++;
}
// Copy remaining elements of arr1[] if any