"""Starter code for the sorting lab.

AUTHOR:
  Titus H. Klinge
  YOUR NAMES HERE"""

def selection_sort(lst):
    """Sorts lst

    PARAMETERS:
      lst : a list of comparable elements

    RETURNS:
      None

    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)):
        smallest = smallest_index(lst, i)              # Finds smallest
        lst[smallest], lst[i] = lst[i], lst[smallest]  # Swaps it into 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:
      smallest : an integer

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

    POSTCONDITIONS:
      * 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:
      None

    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, out):
    """Merges lst1 and lst2 into the list out

    PARAMETERS:
      lst1 : a list of comparable elements
      lst2 : a list of comparable elements
      out : a list

    RETURNS:
       None

    PRECONDITIONS:
      * For any pair of elements x,y in lst1 or lst2,
        x < y is defined
      * lst1 and lst2 are sorted in increasing order
      * len(out) = len(lst1) + len(lst2)

    POSTCONDITIONS:
      * out contains exactly the elements contained in lst1 and lst2
      * out is sorted in increasing order.  That is, 
          * out[i] <= out[i+1] for all reasonable values of i.
      * lst1 and lst2 are destroyed and are empty"""

    i = len(out)-1

    # Repeatedly copies largest element into out until one of the list
    # is completely copied into out
    while len(lst1) > 0 and len(lst2) > 0:
        if lst1[-1] >= lst2[-1]:
            out[i] = lst1.pop()
        else:
            out[i] = lst2.pop()
        i = i - 1
        # print_partial_merge(lst1, lst2, out)

    # Copies any remaining elements into out from lst1
    while len(lst1) > 0:
        out[i] = lst1.pop()
        i = i - 1

    # Copies any remaining elements into out from lst2
    while len(lst2) > 0:
        out[i] = lst2.pop()
        i = i - 1

    # print("final:", out)


def print_partial_merge(lst1, lst2, out):
    """Prints the three lists and only includes the part of out that has been copied so far"""
    partial = out[len(lst1)+len(lst2):]
    print("lst1:", lst1, "\nlst2:", lst2, "\nout:", partial, "\n")