"""
Learning Goals:
 - Analyze and improve the efficiency of different programs
   -- Recognize and trace common sorting algorithms
   -- Understand why different sorting algoritms have different runtimes

"""

def selectionSort(L):
    # Go through each index to move an element into
    for i in range(len(L)-1):
        # Find the smallest element
        minIndex = i
        for j in range(i+1, len(L)):
            if L[j] < L[minIndex]:
                minIndex = j
        # Swap the two elements
        tmp = L[minIndex]
        L[minIndex] = L[i]
        L[i] = tmp
    
def insertionSort(L):
    # Go through each element that needs to be inserted
    for i in range(1, len(L)):
        tmp = L[i]
        j = i-1
        # Move elements forward while they're bigger
        while j >= 0 and L[j] > tmp:
            L[j+1] = L[j]
            j = j - 1
        # Move the original element into its new spot
        L[j+1] = tmp

def mergeSort(L):
    # Base case: empty and one-element lists are already sorted
    if len(L) == 0 or len(L) == 1:
        return
    # Split the list in half, recursively sort each half
    mid = len(L) // 2
    left = L[:mid]
    right = L[mid:]
    mergeSort(left)
    mergeSort(right)
    
    # Merge the two sorted lists back together
    leftIndex = 0
    rightIndex = 0
    i = 0
    # Only need to compare the first unsorted elements,
    # because it's sorted!
    while leftIndex < len(left) and rightIndex < len(right):
        if left[leftIndex] < right[rightIndex]:
            L[i] = left[leftIndex]
            leftIndex = leftIndex + 1
        else:
            L[i] = right[rightIndex]
            rightIndex = rightIndex + 1
        i = i + 1
    # Add any remaining elements to the end of the list
    while leftIndex < len(left):
        L[i] = left[leftIndex]
        leftIndex = leftIndex + 1
        i = i + 1
    while rightIndex < len(right):
        L[i] = right[rightIndex]
        rightIndex = rightIndex + 1
        i = i + 1
    
        
lst = [ 8, 4, 2, 5, 1, 3, 7, 9]
# selectionSort(lst)
# insertionSort(lst)
# mergeSort(lst)
print(lst)