When would you use recursive merge sort over iterative?-CodePudding

Is there ever a situation where you should use a recursive merge sort over an iterative merge sort? Isn't iterative merge sort faster then recursive merge sort? Not to mention recursion makes a lot more calls on the stack which in turn makes it less memory efficeint. What if I have an extremely large dataset that I want to sort? Wouldn't it be bad to use recursion then? Because doesn't excessively deep recursion eventually lead to a stack overflow? Why would you ever use recursive over iterative if it is slower and less memory efficient?

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    current_size = 1
    while current_size < len(arr):
        left = 0
        while left < len(arr)-1:
            mid = left   current_size - 1
            right = min((left   2*current_size - 1), (len(arr)-1))
            merged_arr = merge(arr[left : mid   1], arr[mid   1 : right   1])
            for i in range(left, right   1):
                arr[i] = merged_arr[i - left]
            left = left   current_size*2
        current_size = current_size * 2
    return arr

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i  = 1
        else:
            result.append(right[j])
            j  = 1
    result  = left[i:]
    result  = right[j:]
    return result

def merge_sort_recursive(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort_recursive(left)
    right = merge_sort_recursive(right)
    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i  = 1
        else:
            result.append(right[j])
            j  = 1
    result  = left[i:]
    result  = right[j:]
    return result

I timed these two implementations and found iterative does in fact appear to be faster. Why is that? And why would I ever use recursive then?

CodePudding user response：

Why would you ever use recursive over iterative

Mainly because it's simpler/nicer. For example, your recursive one can sort [3, 1, 4] while your iterative one crashes with an IndexError. No doubt because it's more complicated.

The recursive one is also more balanced, needing fewer comparisons. Left and right are always equally large or differ by just one element. For example, for arr = list(range(2**17)), both do 1114112 comparisons, because both are equally perfectly balanced. But with 2**17 1, the iterative one does 1245184 comparisons while the recursive one only does 1114113. Because the iterative one at the end merges 2^17 elements with 1 element (and that one element happens to be the largest).

I timed these two implementations and found iterative does in fact appear to be faster.

I get the opposite. Even for 2^17 elements, so that the iterative one doesn't have the imbalance issue. Times for sorting three lists both ways:

1.23 seconds merge_sort
0.83 seconds merge_sort_recursive

1.25 seconds merge_sort
0.82 seconds merge_sort_recursive

1.19 seconds merge_sort
0.80 seconds merge_sort_recursive

Code:

from random import shuffle
from time import time

for _ in range(3):
    arr = list(range(2**17))
    shuffle(arr)
    for f in merge_sort, merge_sort_recursive:
        t0 = time()
        f(arr.copy())
        print(f'{time()-t0:.2f} seconds {f.__name__}')
    print()

CodePudding user response：

The iterative version of merge sort is generally faster than the recursive version, because the iterative version uses a loop, which is faster than function calls. Each function call in the recursive version adds a new layer to the call stack, which takes up memory and also takes time to set up and tear down. The iterative version does not have these overhead costs. So yes, you are right in thinking that recursive is less memory efficient I would say.

Additionally, the iterative version of merge sort can be easily parallelized, which can make it even faster on multi-core systems.

That being said, the difference in performance between the two implementations may not be significant for small arrays, but as the array grows larger, the iterative version will be faster.

As far as why you would use it, I would say in most situations that is based on preference. Some people have an easier time thinking recursively than others. So some people find that implementation cleaner. The only time I could think it would physically matter may be if you are in a situation where you really have to worry about memory, or your data set is extremely massive. Which is a kind of rare case in my experience in which case I think you would probably reach for iterative.