Introduction

Merge Sort is a classic sorting algorithm known for its efficiency and stable sorting capabilities, using a divide-and-conquer approach. While the traditional recursive implementation is often discussed, a non-recursive (or iterative) version offers an alternative approach, utilizing an explicit stack or an iterative process to avoid recursion. This article delves into the workings and nuances of Non-Recursive Merge Sort.

Understanding Non-Recursive Merge Sort

Basic Mechanism

The non-recursive version of merge sort operates by iteratively merging subarrays rather than recursively breaking them down. Here's a step-by-step breakdown:

1. Initialization:
   • Begin with a subarray size of 1 (each element is its own subarray).
   • Use an auxiliary array to facilitate merging.
2. Merge Process:
   • Iterate over the list, merging adjacent subarrays of the current size.
   • Double the subarray size after each full pass through the list.
3. Completion:
   • Continue the merging process until the subarray size exceeds the list size, resulting in a completely sorted list.

Advantages

• Space Efficiency: The iterative approach prevents stack overflow issues inherent in recursive implementations.
• Performance: Offers predictable memory usage and is often perceived as faster in practice due to reduced overhead.

Algorithm Complexity

• Time Complexity: $O(n \log n)$ in all cases (best, worst, and average).
• Space Complexity: $O(n)$ due to the auxiliary array, regardless of using recursive or non-recursive merge sort.

Technical Explanation and Pseudocode

The essence of non-recursive Merge Sort can be captured by the following pseudocode:

• Initial Array: [5, 2, 9, 1, 5, 6]
• Subarray Size 1: [2, 5, 1, 9, 5, 6]
• Subarray Size 2: [1, 2, 5, 9, 5, 6]
• Subarray Size 4: [1, 2, 5, 5, 6, 9]
• Final Sorted Array: [1, 2, 5, 5, 6, 9]
• Recursive Merge Sort:
  • Utilizes implicit stack memory managed by function calls.
  • Simpler to implement but can consume more stack space.
• Non-Recursive Merge Sort:
  • Employs explicit looping mechanisms, leveraging an auxiliary array.
  • More robust regarding stack memory concerns, can be more performant for limited stack environments.