Sorting Algorithms and arrays

Question 1

merge sort

Answer 1

def merge_sort(lst):
    # base case, we've reached the list of size 1
    if len(lst) > 1:
        # split the list
        mid = len(lst) // 2
        left = lst[:mid]
        right = lst[mid:]

    # recursively iterate through each half of the list
    merge_sort(left)
    merge_sort(right)

        # create pointers for left, right, and the original list
        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                # add the smaller element to the list
                lst[k] = left[i]
                i += 1
            else:
                lst[k] = right[j]
                j += 1
            k += 1

        # iterate through any remaining items in the halves
        while i < len(left):
            lst[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            lst[k] = right[j]
            j += 1
            k += 1

Time complexity:
O(n * logn)
The algorithm works in O(n * logn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.

Space Complexity:
O(n)
We create a mini list left and right per each halving of items in the list. At the time of the final merge the sum of space of these lists will just equal n because they are half of the list.

Credit:
I pulled and modified this algo implementation from this awesome article by educative: https://www.educative.io/edpresso/merge-sort-in-python