Pycharm error where it is running hidden in the background
du -d 1
rm -rf ./Pycharm.../

rm -rf .PyCharmCE2013.2/system

TO IMPORT FILE INTO PYCHARM PYTHON CONSOLE:
from timsort import *

FOR EXAM, IF YOU ARE ABLE TO EXPLAIN TO YOURSELF WHAT YOU WROTE, YOU WILL BE FINE. I RECOMMEND REDOING LABS, GOING OVER PAST EXAMS WITH YOUR FRIENDS (show them utm past exams repo), REDOING PREPS, GOING OVER ASSIGNMENTS AND REDOING THE MIDTERM.
--------------------------------------------------------------------------------------------------------------------------
Todays lab is more of a coding challenge. In lecture you probably covered none mutable sorting algorithms like bubble or selection sort which just return a new list. Now we are strictly working with a mutating algorithm Mergesort actually mutates the list.

This lab is rather difficult and Bogdan left in the TA notes most students will not get passed the Third task. Thus feel free to complete the first two tasks and attempt the fifth one because they are the shortest (in terms of code) and I believe the most important takeaways for this lab. OR if youd like, feel free to study for this or other exams it really doesnt matter. I will take up task 1, 2 , 5 and maybe 3 at the end but for now, please feel free to work on whatever youd like. There is still a quiz at the end.

TASK 1:------------------------------------------------
The hardest part of understanding task 1 is understanding what a "run" is, so lets cover this together.
	"""
    >>> find_runs([1, 4, 7, 10, 2, 5, 3, -1])
    [(0, 4), (4, 6), (6, 7), (7, 8)]
    >>> find_runs([0, 1, 2, 3, 4, 5])
    [(0, 6)]
    >>> find_runs([10, 4, -2, 1])
    [(0, 1), (1, 2), (2, 4)]
    """

What does this output mean? It goes through the indexes of sorted arrays within the list. Each starts at index X and go up to the index that is still sorted but remember its not inclusive.

def find_runs(lst: list) -> List[Tuple[int, int]]:
    runs = []

    # Keep track of the start and end points of a run.
    run_start = 0
    run_end = 1
    while run_end < len(lst):
        # How can you tell if a run should continue?
        # How can you tell if a run is over?
        if lst[run_end - 1] <= lst[run_end]:
            run_end += 1
        else:
            # Once a run is over, make sure you add it to runs!
            runs.append((run_start, run_end))
            run_start = run_end
            run_end += 1

    # Append the last run
    runs.append((run_start, run_end))
    return runs

So where were doing here is starting at the first index. We keep iterating our run_end index counter until we reach an element that is out of order. Once its out of order, we append our tuple of indexes including the index we started at and the index we went up to but not including. Now we reset the run_start by making it the current end of the run we ended and iterate plus to begin the next iteration. Once the loop finishes, we will need to append the final run without going out of range so we manually add the last element to the latest run.

TASK 2:------------------------------------------------
So now that we have a list of numbers and the list of runs (that is a list of sorted indexes), we want to simple merge all the indexed tuples into one final list. So if we take the example in the doctest:
lst = [1, 4, 7, 10, 2, 5, 3, -1]
This will produce the runs [(0, 4), (4, 6), (6, 7), (7, 8)] which if we were to break up into individual sub lists, we have [1,4,7,10] and [2, 5] and [3] and [-1]
So we want to build a function that will merge this 4 sublists into a single list that will output
[-1,1,2,3,4,5,7,10]
def timsort(lst: list) -> None:
    runs = find_runs(lst)

    # Treat runs as a stack and repeatedly merge the top two runs
    # When the loop ends, the only run should be the whole list.
    # HINT: you should be able to use the "merge" function provided
    # in this file.

    while len(runs) > 1:
        mid1, end = runs.pop()
        start, mid2 = runs.pop()

        _merge(lst, start, mid1, end)
        runs.append((start, end))

So what we are doing is applying the mergesort function onto the indexes we are given, one at a time. So when we can our list of tuples of indexes from find_runs, we essentially parse through those runs, getting the indexes needed to call mergesort(). So lets go through the first iteration together. If we have the runs [(0, 4), (4, 6), (6, 7), (7, 8)], we want to perform two pops. Why? Because the _merge() function sort needs 3 arguments, the starting index, the middle index and the ending index. So from these two tuples that we popped from the end of runs [(6, 7), (7 ,8)], what should be our 3 indexes? It should be start at index 6, 7 is our middle index and 8 is our end index. So with those values, we can simply call _merge() to mutate out list. Now I mentioned we keep creating a new tuple each time we call _merge() and we need to update runs everytime we finishing executing _merge() so thus, we create a new tuple with the starting and ending indexes we used and append that to runs to it can be used for the next iteration.

If you wanted to, you could have also done pop(0) or any other alternative where you are working with the first or front of the list of runs, it would still work the same. What the code is doing algorithmically is calling mergesort on two tuples, creating a new one, then calling mergesort on the newly created tuple and the next tuple in runs and so on till all indexes have been properly merge sorted.

TASK 3:------------------------------------------------
def find_runs2(lst: list) -> List[Tuple[int, int]]:
    runs = []

    # Keep track of the start and end points of a run.
    run_start = 0
    run_end = 1

    # Hint: this is similar to find_runs, except
    # you'll need to keep track of whether the "current run"
    # is ascending or descending.
    asc = None

    while run_end < len(lst):
        if asc is None:
            # Figure out if the run is ascending or descending
            # Note: a better approach would make the = case
            # not set asc, so that we can make [3, 3, 2] one run
            asc = lst[run_end - 1] <= lst[run_end]
            run_end += 1
        elif asc and lst[run_end - 1] <= lst[run_end]:
            # Continue an ascending run
            run_end += 1
        elif not asc and lst[run_end - 1] >= lst[run_end]:
            # Continue a descending run
            run_end += 1
        else:
            # Once a run is over, make sure you add it to runs!
            runs.append((run_start, run_end))

            # If the run was descending, reverse it.
            if asc is False:
                lst[run_start:run_end] = reversed(lst[run_start:run_end])

            run_start = run_end
            run_end += 1
            asc = None

    # Append the last run. The check is necessary because the last run
    # detected in the loop might already have ended at the end of the list.
    if run_end == len(lst):
        runs.append((run_start, run_end))

        # If the run was descending, reverse it.
        if asc is False:
            lst[run_start:run_end] = reversed(lst[run_start:run_end])

    return runs
TASK 4:------------------------------------------------

TASK 5:------------------------------------------------
For this task, your code should work the exact same are the given _merge() function so you can create doctests where you have an unsorted list and given the index 0 and len(lst) -1, (your start and end indexes) you new _merge2() function should be able to sort the list.

def _merge2(lst: list, start: int, mid: int, end: int) -> None:
    """Sort the items in lst[start:end] in non-decreasing order.

    Precondition: lst[start:mid] and lst[mid:end] are sorted.
    """
    # Store the "A" run in a temporary list.
    temp = lst[start:mid]
    left = 0
    right = mid
    curr = start  # Current position in lst to fill in.

    while left < len(temp) and right < end:
        if temp[left] < lst[right]:
            lst[curr] = temp[left]
            left += 1
        else:
            lst[curr] = lst[right]
            right += 1
        curr += 1

    # Copy over remaining elements
    lst[curr:curr + len(temp) - left] = temp[left:]

So what _merge2() is doing is pretty silly because by the PreCondition, we assume already that the inputted list is not entirely sorted but, its sorted in two separate halves. For example the input would could have would be something like [1,3,5,7,2,4,6,8] right? We have a list that is not in sorted order but it has two halves where the [start:mid] list is the list [1,3,5,7] and the [mid:end] list is the list [2,4,6,8]. So what we are trying to do is manually merge the two lists by overriding our already existing list. Ignoring code, what we are trying to is create a duplicate of the first half list, in our case [1,3,5,7] then we want to iterate through all the indexes in both lists and make that comparison. So we start at the front of both lists, we have [1,3,5,7] and [2,4,6,8]. Looking at our duplicate of [start:mid], we compare [1] with [2], see that 1 < 2 so we set the first index in our list to [1]. Moving onto the next index, we compare [3] with [2], see that 2 < 3 so we set the second index in our list to [2] and so on. The confusing part I believe it how we are mutating the same list we are working on, not returning a new list. You can use temporary lists if you would like, but thats part of the challenge. If we were to do this csc108 style, we would create a new list and compare values between the two lists. So you would have something like this:

lst1 = [1,3,5,7]
lst2 = [2,4,6,8]
result = []
leftindex = 0
rightindex = 0
for i in range(len(lst1)):
	if lst1[rightindex] > lst2[leftindex]:
		result.append(lst1[rightindex])
		rightindex++;
	else:
		result.append(lst2[leftindex])
		leftindex++;
return result + [rest of the remaining lst]


And we reach the end of our lists, since we dont always know what the length of the sublists are, we need to append all the remaining elements. So say we had the lists [1,3,5,7] and [2,4,6,8,10,12,14], our while loop will only iterate through the first 4 indexes (obviously because if we tried to iterate to the fifth index of the first sublist, we would be thrown an error), then if our code is successfully done in the while loop, we should have the result list of [1,2,3,4,5,6,7,8] and we are left with a sublist [10,12,14] so since we know that this list is sorted by the precondition, we can simply append it to our resulting list to get the value [1,2,3,4,5,6,7,8,10,12,14].
TASK 6:------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------
Quiz 11:
def remove_duplicates(lst):
    """Return a sorted list containing the same values as <lst>, but without duplicates.

    Precondition: <lst> is sorted.

    @type lst: list
    @rtype list

    >>> remove_duplicates([1, 2, 2, 2, 3, 10, 10, 20])
    [1, 2, 3, 10, 20]
    """
    new_lst = []
    prev_item = None
    for item in lst:
        if item != prev_item:
            new_lst.append(item)
        prev_item = item
    return new_lst


Know the property that the list is sorted. So we can check that every item is not equal to the next item, and thus we can append it to our new list. Noticed I said NEW LIST because this function is non-mutating the inputted list, we need to create a new one. HOMEWORK: TRY TO MAKE THIS FUNCTION WORK ON THE ON THE LIST THATS PASSED IN. IE DONT RETURN A NEW LIST, RETURN THE SAME ONE.