Introduction

Merge sort is a classic divide-and-conquer algorithm that is widely used due to its efficiency and stability. Unlike quicksort, which often has a worse-case time complexity of $O(n^2)$, merge sort consistently maintains a time complexity of $O(n \log n)$. In typical recursive implementations, merge sort continually divides the array into halves until each half contains a single element, then merges the sorted halves to produce the sorted array. However, an iterative approach is sometimes preferable when recursion might cause stack overflow due to limited space for recursion stack entries.

Iterative Merge Sort

An iterative implementation of merge sort avoids the recursive stack by using an iterative construct, typically a loop. The basic idea is to iteratively merge subarrays in a bottom-up manner.

Process Description

1. Initialize Subarray Size: Start with a subarray size of 1.
2. Merge Pairs of Subsequent Subarrays: Iterate over the array and merge pairs of subsequent subarrays. The subarray size doubles on each loop iteration.
3. Repeat: Continue doubling the subarray size and repeat until the array is completely sorted.

Example

Let's walk through an example of iterating through a merge sort on an array: `[38, 27, 43, 3, 9, 82, 10]`.

1. Initial Array: `[38, 27, 43, 3, 9, 82, 10]`
2. Subarray Size `s = 1`:
   • Merge `[38]` and `[27]` → `[27, 38]`
   • Merge `[43]` and `[3]` → `[3, 43]`
   • Merge `[9]` and `[82]` → `[9, 82]`
   • `[10]` remains
   • Result: `[27, 38, 3, 43, 9, 82, 10]`
3. Subarray Size `s = 2`:
   • Merge `[27, 38]` and `[3, 43]` → `[3, 27, 38, 43]`
   • Merge `[9, 82]` and `[10]` → `[9, 10, 82]`
   • Result: `[3, 27, 38, 43, 9, 10, 82]`
4. Subarray Size `s = 4`:
   • Merge `[3, 27, 38, 43]` and `[9, 10, 82]` → `[3, 9, 10, 27, 38, 43, 82]`
   • Result: `[3, 9, 10, 27, 38, 43, 82]`

Code Implementation

Below is a simple Python implementation of the iterative merge sort:

• Space Efficiency: Avoids recursion overhead by using an iterative structure.
• Consistent Performance: Worst-case time complexity remains $O(n \log n)$.
• Non-recursive Implementation: Better for systems with limited stack size.
• Complexity in Implementation: Generally more complex than the recursive approach.
• Higher Space Usage: Still requires additional space for merging.