# Take two sorted lists, the_list[p : q+1] and the_list[q+1 : r+1],
# and merge them into the_list[p : r+1].
def merge(the_list, p, q, r):
    # Make a copy of the list items.
    left = the_list[p: q + 1]
    right = the_list[q + 1: r + 1]

    # Until we've gone through one of left and right, move
    # the smallest unmerged item into the next position in
    # the_list[p : r+1].

    i = 0       # index into left
    j = 0       # index into right
    k = p       # index into the_list[p : r+1]

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            the_list[k] = left[i]
            i += 1
        else:
            the_list[k] = right[j]
            j += 1
        k += 1

    # We've gone through one of left and right entirely.
    # Copy the remainder of the other to the end of the_list[p : r+1].

    # If left has remaining items, copy them into the_list, using list slices.
    if i < len(left):
        the_list[k: r + 1] = left[i:]

    # If right has remaining items, copy them into the_list, using list slices.
    if j < len(right):
        the_list[k: r+1] = right[j:]

# Sort the_list[p : r+1], using merge sort.
def merge_sort(the_list, p=0, r=None):

    # If using the default parameters, sort the entire list.
    if r == None:
        r = len(the_list) - 1

    # base case:
    if p >= r:
        return

    # recursive case
    q = (p + r) // 2                 # midpoint of p and r
    merge_sort(the_list, p, q)      # recursively sort the_list[p : q+1]
    merge_sort(the_list, q+1, r)    # recursively sort the_list[q+1 : r+1]
    merge(the_list, p, q, r)        # and merge them together

grade_list = [89, 45, 85, 81, 77, 94, 22, 79, 92, 91]
print(str(grade_list))