Implementing a Memory‑Efficient Stable Merge Sort for Large Python Datasets

Desired Outcome

Build a stable merge sort that keeps memory usage to O(n) while handling lists of several hundred million elements on Python 3.10+. The algorithm should avoid recursion limits, remain stable, and be competitive with sorted() on large, unsorted inputs.

Prerequisites

• Python 3.10+ installed in a virtual environment.
• Basic understanding of recursion limits (sys.getrecursionlimit()) and memory profiling tools like tracemalloc.
• Familiarity with list slicing and the list.sort() method for reference.

Procedure

1. Create a single auxiliary buffer. Allocate a list of the same length as the input. This buffer will hold temporary merged data during each pass.

   def merge_sort_iterative(arr):
       n = len(arr)
       buffer = [None] * n  # auxiliary buffer
       # further steps follow
   

2. Iterative merge passes. Instead of recursive splits, perform a bottom‑up merge. Start with sub‑lists of size 1 and double the width each pass.

   width = 1
   while width < n:
       for left in range(0, n, 2 * width):
           mid = min(left + width, n)
           right = min(left + 2 * width, n)
           merge(arr, buffer, left, mid, right)
       width *= 2
   

3. Merge function using the buffer. Copy the relevant slice into the buffer, then merge back into arr.

   def merge(arr, buf, left, mid, right):
       i, j, k = left, mid, left
       while i < mid and j < right:
           if arr[i] <= arr[j]:
               buf[k] = arr[i]
               i += 1
           else:
               buf[k] = arr[j]
               j += 1
           k += 1
       while i < mid:
           buf[k] = arr[i]
           i += 1; k += 1
       while j < right:
           buf[k] = arr[j]
           j += 1; k += 1
       # copy back
       arr[left:right] = buf[left:right]
   

4. Insertion‑sort shortcut for tiny sub‑lists. When width falls below a threshold (e.g., 32), switch to insertion sort to reduce overhead.

   def insertion_sort(arr, left, right):
       for i in range(left + 1, right):
           key = arr[i]
           j = i - 1
           while j >= left and arr[j] > key:
               arr[j + 1] = arr[j]
               j -= 1
           arr[j + 1] = key
   

5. Replace the merge pass for small widths. In the main loop, if width < insertion_threshold, call insertion_sort instead of merge.
6. Optional: Preserve original indices for a key‑based stability wrapper. If stability appears broken, wrap elements with their original index:

   arr = [(value, idx) for idx, value in enumerate(arr)]
   # run merge_sort_iterative
   # extract sorted values preserving order
   arr = [value for value, _ in arr]
   

Expected Checks

1. Stability validation. Sort a list of tuples where the first element is the key and the second is a tie‑breaker. After sorting, confirm that tuples with equal keys retain the original relative order.

   data = [(5, 'a'), (5, 'b'), (3, 'c'), (5, 'd')]
   merge_sort_iterative(data)
   # Expected: [(3, 'c'), (5, 'a'), (5, 'b'), (5, 'd')]
   

2. Memory profiling. Use tracemalloc to capture peak memory.

   import tracemalloc
   tracemalloc.start()
   merge_sort_iterative(big_list)
   peak = tracemalloc.get_traced_memory()[1]
   print(f"Peak memory: {peak / (1024 ** 2):.2f} MB")
   tracemalloc.stop()
   

   With a 10‑million element list, the peak should stay below 1.5× the size of the input (≈15 MB for 10 M integers).

3. Benchmarking. Compare run times against sorted() using timeit.

   import timeit
   print(timeit.timeit(lambda: merge_sort_iterative(lst.copy()), number=1))
   print(timeit.timeit(lambda: sorted(lst), number=1))
   

   For random data >10 M elements, the custom sort should be within 10–20% of sorted() while using less memory.

Recovery Options

• Chunked processing. If the auxiliary buffer causes an out‑of‑memory error, split the input into smaller chunks, sort each independently, and then perform a multi‑way merge using a heap. This trades a few extra passes for lower peak memory.
• Fallback to Timsort. If stability tests fail, replace the merge logic with Python’s built‑in sorted() (which uses Timsort) or wrap elements with original indices as shown above.
• Adjust insertion threshold. A higher threshold can improve performance on nearly sorted data, but may increase memory usage. Tune the value based on profiling results.

Limitations & Practical Checks

• Nearly sorted inputs may cause the algorithm to perform more merges than necessary. In such cases, consider hybridizing with Timsort or increasing the insertion threshold.
• Large auxiliary buffers can still trigger MemoryError on low‑RAM systems. Monitor peak memory with tracemalloc before scaling up.
• Because the algorithm is iterative, recursion depth is not an issue, but ensure that no inadvertent recursive calls remain in helper functions.

To verify correctness after any change, rerun the stability unit test and memory profiling. If memory spikes, reduce insertion_threshold or process data in smaller batches.

Concrete Example

Below is a minimal, self‑contained script that demonstrates the full workflow, including stability testing and memory profiling.

import sys, random, tracemalloc

# Configuration
INSERTION_THRESHOLD = 32

# Merge sort implementation

def merge_sort_iterative(arr):
    n = len(arr)
    buffer = [None] * n
    width = 1
    while width < n:
        for left in range(0, n, 2 * width):
            mid = min(left + width, n)
            right = min(left + 2 * width, n)
            if width < INSERTION_THRESHOLD:
                insertion_sort(arr, left, right)
            else:
                merge(arr, buffer, left, mid, right)
        width *= 2


def merge(arr, buf, left, mid, right):
    i, j, k = left, mid, left
    while i < mid and j < right:
        if arr[i] <= arr[j]:
            buf[k] = arr[i]; i += 1
        else:
            buf[k] = arr[j]; j += 1
        k += 1
    while i < mid:
        buf[k] = arr[i]; i += 1; k += 1
    while j < right:
        buf[k] = arr[j]; j += 1; k += 1
    arr[left:right] = buf[left:right]


def insertion_sort(arr, left, right):
    for i in range(left + 1, right):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Stability test

def test_stability():
    data = [(5, 'a'), (5, 'b'), (3, 'c'), (5, 'd')]
    merge_sort_iterative(data)
    assert data == [(3, 'c'), (5, 'a'), (5, 'b'), (5, 'd')]

# Memory profiling

def profile_memory(size):
    lst = [random.randint(0, 1000000) for _ in range(size)]
    tracemalloc.start()
    merge_sort_iterative(lst)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak / (1024 ** 2)  # MB

if __name__ == '__main__':
    test_stability()
    for sz in [10**5, 10**6, 10**7]:
        peak_mb = profile_memory(sz)
        print(f"Size {sz:,} – Peak memory: {peak_mb:.2f} MB")

Conclusion

By using a single auxiliary buffer, an iterative merge strategy, and a lightweight insertion‑sort shortcut, you can create a stable, memory‑efficient sort that scales to very large lists without hitting Python’s recursion limits. Regularly validate stability and memory usage with the provided checks to keep the implementation robust across diverse workloads.