"""Starter code for the sorting lab.

Author: Titus H. Klinge and YOUR NAMES HERE"""

def selection_sort(lst):
    """Sorts lst

    Parameters:
        lst: a list of comparable elements

    Returns:
        Nothing; called for the side effect

    Preconditions:
        * For any pair of elements x,y in lst,
          x < y is defined

    Postconditions:
        * lst is reorganized in increasing order.  That is, 
            * lst[i] <= lst[i+1] for all reasonable values of i.
        * no elements are added or removed from lst."""
    for i in range(len(lst)):
        s = smallest_index(lst, i)
        lst[s], lst[i] = lst[i], lst[s]  # Swaps s and i


def smallest_index(lst, start):
    """Finds the index of smallest element in lst such that index >= start

    Parameters:
        lst: a list of comparable elements
        start: an integer index of lst

    Returns:
        the index of the smallest element in lst[start:]

    Preconditions:
        * len(lst) > 0
        * 0 <= start < len(lst)

    Postconditions:
        * smallest refers to the return valued
        * 0 <= smallest < len(lst)
        * lst[smallest] is the smallest element in lst starting
          at index start, that is
              lst[smallest] <= lst[i]
          for all indices i satisfying start <= i < len(lst)"""
    smallest = start
    for i in range(start+1, len(lst)):
        if lst[i] < lst[smallest]:
            smallest = i
    return smallest


def merge_sort(lst):
    """Sorts lst

    Parameters:
      lst: a list of comparable elements

    Returns:
      Nothing; called for the side effect

    Preconditions:
      * For any pair of elements x,y in lst,
        x < y is defined

    Postconditions:
      * the elements of lst are rearranged and sorted in increasing order.  That is, 
          * lst[i] <= lst[i+1] for all reasonable values of i."""
    if len(lst) > 1:
        mid = len(lst) // 2
        left, right = lst[:mid], lst[mid:]
        merge_sort(left)
        merge_sort(right)
        merge(left, right, lst)

def merge(lst1, lst2, lst3):
    """Takes two sorted lists, combines them, and copies them into the third list

    Parameters:
        lst1: a sorted list
        lst2: a sorted list
        lst3: a list

    Returns:
        Nothing; called for the side effect

    Preconditions:
        * lst1 is sorted, i.e., that
            lst1[i] <= lst1[i+1] for all reasonable i
        * lst2 is sorted, i.e., that
            lst2[i] <= lst2[i+1] for all reasonable i
        * len(lst3) == len(lst1) + len(lst2)

    Postconditions:
        * lst3 contains exactly the union of the elements
          of lst1 and lst2
        * lst3 is sorted, i.e., that
            lst3[i] <= lst3[i+1] for all reasonable i"""

    i1, i2, i3 = 0, 0, 0

    # While there is at least one element from each list
    # to add to lst3
    while i1 < len(lst1) and i2 < len(lst2):
        # Find the smallest next element from the lists
        if lst1[i1] < lst2[i2]:
            # If it is in lst1, copy it into lst3
            lst3[i3] = lst1[i1]
            i1 = i1 + 1
        else:
            # If it is in lst2, copy it into lst3
            lst3[i3] = lst2[i2]
            i2 = i2 + 1
        i3 = i3 + 1
        # print("lst1:", lst1, "\nlst2:", lst2, "\nlst3:", lst3, "\n")

    # If there are any elements remaining in lst1, copy them
    while i1 < len(lst1):
        lst3[i3] = lst1[i1]
        i1 = i1 + 1
        i3 = i3 + 1

    # If there are any elements remaining in lst2, copy them
    while i2 < len(lst2):
        lst3[i3] = lst2[i2]
        i2 = i2 + 1
        i3 = i3 + 1

    # print("final:", lst3)