Stepping through the Recursive Calls of Merge Sort

Merge sort follows the divide-and-conquer approach, repeatedly breaking down its input into smaller, more manageable parts and applying a single algorithm to each subpart to eventually merge all parts into a sorted list. The algorithm is efficient, performing at worst Θ(nlogn). In this post, I will walk through the merge sort algorithm with careful attention to returned results of recursive calls. If you have trouble visualizing the results of functions that have multiple recursive calls, I encourage you to read on! 😊


We will be stepping through the code sample below, in which our merge_sort algorithm follows the the typical divide-and-conquer approach and merge is used as a helper function to merge our subarrays into sorted arrays.
def merge_sort(array):
if len(array) <= 1: return array mid = len(array) // 2 left = merge_sort(array[:mid]) right = merge_sort(array[mid:]) return merge(left, right) def merge(left, right): left_index = 0 right_index = 0 result = [] while left_index < len(left) and right_index < len(right): if left[left_index] < right[right_index]: result.append(left[left_index]) left_index += 1 else: result.append(right[right_index]) right_index += 1 result += left[left_index:] result += right[right_index:] return result Example The array we pass into merge_sort will be [17,1,9,22,8,40,21,41]. The sorted output will be [1,8,9,17,21,22,40,41]. Recursive Tree Map After stepping through the merge_sort function, we end up with a recursive calls that look like this: These recursive calls are stored in the left and right variables in merge_sort. Each call is then passed into merge to actually merge each individual array. We start at the bottom of our tree and merge back up. Steps 1 left = merge_sort([17]) right = merge_sort([1]) merge(left,right) = [1,17] 2 left = merge_sort([9]) right = merge_sort([22]) merge(left,right) = [9,22] 3 left = merge_sort([8]) right = merge_sort([40]) merge(left,right) = [8,40] 4 left = merge_sort([21]) right = merge_sort([41]) merge(left,right) = [21,41] 5 left = merge_sort([1,17]) right = merge_sort([9,22]) merge(left,right) = [1,9,17,22] 6 left = merge_sort([8,40]) right = merge_sort([21,41]) merge(left,right) = [8,21,40,41] 7 left = merge_sort([1,9,17,22]) right = merge_sort([8,21,40,41]) merge(left,right) = [1,8,9,17,21,22,40,41] Since we've reached the top of our tree, we know that all necessary recursive calls have been made. We return the result of the final recursive call, which is the sorted array [1,8,9,17,21,22,40,41].