Divide and Conquer

"""
This algorithm divides the original problem into smaller sub-problems, solves the sub-problems recursively, and combines their solutions to get the solution to the original problem.

Pseudocode:

# divide and conquer - takes an array/subarray
    # handle the base case w/ 0 or 1 elements (no dividing-and-conquering/recursion needed)
    # recursively handle left and right halves
    # merge them:
    # handle the case whether either half could be next
    # add any remainder from either half
"""

def merge_sort(arr):
    # edge case: handle the edge case where the list is too short to need processing
    if len(arr) <= 1:
        return

    # recurse: recursively call this function on the left and right halves of the list
    middle = len(arr) // 2
    L = arr[:middle]
    R = arr[middle:]
    merge_sort(L)
    merge_sort(R)

    # merge: merge the two sorted halves
    # first handle the case where either of the two halves could have the next element
    l = r = a = 0
    while l < len(L) and r < len(R):
        if L[l] < R[r]:
            arr[a] = L[l]
            l += 1
        else:
            arr[a] = R[r]
            r += 1
        a += 1

    # copy remainder: ...then handle the case where only one half has the next element
    while l < len(L):
        arr[a] = L[l]
        l += 1
        a += 1
    while r < len(R):
        arr[a] = R[r]
        r += 1
        a += 1


arr = [40, 10, 5, 4, 3]
merge_sort(arr)
print(arr)