csc148_slog_sorting_algorithm_and_linked_traversal

    In the week 9 of csc148, we learned some sorting algorithm and their time complexity in the lecture, and we learned how to traverse the binary tree into linked list in the lab.
    The first sorting algorithm is selecting sort. The basic idea is to select the max(min) element and swap it with the first element. And do it for the sublist(list[i:]) over and over again. The time complexity is O(n^2), because it needs 1+2+3+...n steps to finish.
    The second sorting algorithm is quick sort. The basic idea is to quick sort(recursion here!) the set of elements which are less than L[0], quick sort(recursion) the set of elements which are greater than L[0], then return the first stuff + L[0] + second stuff. The worst case time complexity is O(n^2) when L[0] is always the smallest(greatest) element for every recursion. The best case time complexity is O(n*logn) because we split all the elements into halves and for every split we need n operations to get them together.
    The third sorting algorithm is merge sort, which seems more complicated. I found a picture in Wiki which I think perfectly explain how merge sort works. The basic idea of  the merge sort is to merge(We have to write a helper function about merge) the two halves which is merge sorted(recursion here!). The time complexity is O(n*logn) even if it is the worse case.
 

    The fourth sorting algorithm is counting sort. The time complexity is O(n+k), k is the greatest element in the list, which seems perfect. The basic idea is to create another list2 and use the index of list2 to indicate the number. For example, if the list to sort is [1,2,3,5,1], then we create list2, which is [0,2,1,1,0,1]. list2[1] = 2, indicating that there are two '1's. list2[5] = 1, indicating that there is a '5'. Then we have to create a sorted list by traversing list2 (list2[0] = 0, do nothing, list2[1] = 2, append two '1', list2[2] = 1, append a '2'......).
    Currently, I can get time complexity of some algorithm intuitively but I can't prove the time complexity rigorously. Maybe I will learn how to deal with it in 200-level and 300-level csc courses.
    In the lab, we learned how to traverse a binary tree and return two linked list nodes(In the past, we have learned how to return a normal python list). At first, I am very confused about why we have to return two linked list nodes(first node of the traversal, last node of the traversal) rather than one linked list node and I just have no idea to construct this recursive function. After searching in Google, I find that the perfect way is to call recursion on the left sub tree and right sub tree, link the last node of the left sub tree to the root, link root to the first node of the right sub tree, then all nodes are linked!!