"""
Learning Goals:
 - Recognize the general algorithm and trace code for three algorithms: selection sort, insertion sort, and merge sort
 - Compute the Big-O runtimes of selection sort, insertion sort, and merge sort
"""

def swap(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp

###

def selectionSort(lst):
    # i is the index of the first unsorted element
    # everything before it is sorted
    for i in range(len(lst)-1):
        # find the smallest element
        currentMinIndex = i
        for j in range(currentMinIndex + 1, len(lst)):
            if lst[j] < lst[currentMinIndex]:
                currentMinIndex = j
        swap(lst, i, currentMinIndex)
    return lst

lst = [70, 65, 41, 43, 100, 35, 74, 60, 94, 41]
print(selectionSort(lst))

###

def insertionSort(lst):
    for i in range(1, len(lst)):
        unsortedIndex = i
        while (unsortedIndex > 0) and (lst[unsortedIndex] < lst[unsortedIndex-1]):
            swap(lst, unsortedIndex, unsortedIndex-1)
            unsortedIndex -= 1
    return lst

lst = [70, 65, 41, 43, 100, 35, 74, 60, 94, 41]
print(insertionSort(lst))

###

def mergeSort(lst):
    # base case: 0-1 elements are sorted.
    if len(lst) < 2:
        return lst
    # divide
    mid = len(lst) // 2
    front = lst[:mid]
    back = lst[mid:]
    # conquer by sorting
    front = mergeSort(front)
    back = mergeSort(back)
    # combine sorted halves
    return merge(front, back)

def merge(front, back):
    result = [ ]
    i = 0
    j = 0
    while i < len(front) and j < len(back):
        # only compare first two- guaranteed to be smallest due to sorting
        if front[i] < back[j]:
            result.append(front[i])
            i = i + 1
        else:
            result.append(back[j])
            j = j + 1
    # add remaining elements (only one still has values)
    result = result + front[i:] + back[j:]
    return result

lst = [70, 65, 41, 43, 100, 35, 74, 60, 94, 41]
print(mergeSort(lst))