Merge Sort
August 13, 2019
Code Snippets
Classic CS algorithm in Python, annotated with lots of comments
def merge_array(arr, left, right: list) -> list: # combine left and right sides # counters for tracking the left and right side # and total data written leftCnt = rightCnt = totalCnt = 0 # Loop thru data in left and right # since one side can have one more element # we are using two counters while leftCnt < len(left) and rightCnt < len(right): if left[leftCnt] < right[rightCnt]: arr[totalCnt] = left[leftCnt] leftCnt += 1 else: arr[totalCnt] = right[rightCnt] rightCnt += 1 totalCnt += 1 # empty any remain from left and right while leftCnt < len(left): arr[totalCnt] = left[leftCnt] leftCnt += 1 totalCnt += 1 while rightCnt < len(right): arr[totalCnt] = right[rightCnt] rightCnt += 1 totalCnt += 1 return arr def merge_split(arr: list) -> list: # actual merge_sort function, without error handling # :: recursivily called # base case to return if len(arr) > 1: # get middle point mid = len(arr) // 2 # store a left/right side left = arr[:mid] right = arr[mid:] # recusively call ourselves merge_sort(left) merge_sort(right) # meat, this is actually performs the sort arr = merge_array(arr, left, right) return arr def merge_sort(arr: list) -> list: # BigO (n log n) # :: log n, as this is a divide algo # :: n, as we need to merge the halfs back # 0 Elements: Exception if len(arr) == 0: raise Exception('No Elements') # 1 Element: Early Return if len(arr) == 1: return arr # call the actual merge_sort arr = merge_split(arr) return arr
Tests…
import pytest import random from merge_sort import merge_sort def test_func_exists(): merge_sort([1]) def test_sort(): input = [1, 5, 3, 2, 4] actual = merge_sort(input) expected = [1, 2, 3, 4, 5] assert actual == expected def test_all_same(): input = [3, 3, 3, 3, 3, 3, 3] actual = merge_sort(input) expected = [3, 3, 3, 3, 3, 3, 3] assert actual == expected def test_sort_zero(): with pytest.raises(Exception): merge_sort([]) def test_sort_lots(): input = [] for x in range(1000): input.append(random.randint(1, 1000)) actual = merge_sort(input) expected = input expected.sort() assert actual == expected