SLOG - week11: Sorting and Efficiency
Sorting. It's the thing which you sometimes wish to use. There are moments when you extremely want to use sorting techniques to solve or sort things out. For example, every time when professor spreads all the midterm papers or any handed-work at class and says, come and get it. Huh. Imagine that episode for a moment, the whole class is just like bees running downward towards a front giant-lenghty desk. At that time, I wish we had sorting machine for that....

So there are so many sorting algorithms that each can be effective in a different way. As we covered at class some of them: merge sort, quick sort, bubble sort, tim sort, selection, insertion and etc. Let's shortly give a brief explanation to each of these algorithms.
Buble sort has a sorted and an unsorted part.  At every pass, it traverses unsorted part from right to the left thereby swaps unordered elements. Hence, bubble  at one pass puts one element at a proper place, so it relatively takes n passes, and performs n -1 comparisons and swaps at each pass. Bubble sort can be efficient to use on a nearly sorted list because it will not swap entire list.
Selection sort also has a sorted and unsorted part. But the difference is initially its sorted part will be empty, and entire list will be unsorted part. At every pass, it finds the smallest element in the unsorted part and swaps with the first element of the unsorted part. So the process takes n times to sort entire list.
Insertion is a bit similar to selection. It also has sorted and unsorted parts. Initally, sorted part is empty and presumes an entire list as unsorted. At every pass, it takes first element in the unsorted and puts it at the right place, and is repeated till the list gets sorted from right to left. It will also keep each element at each pass not to have space problem. Insertion is slower compare to selection sort on average cases and performs more swaps, but it's good on nearly sorted list. The time complexity of bubble, selection and insertion sorts are O(n^2). And all these three sorts are not efficient to use on a large size of data.
Quicksort recursively sorts list. We pick a pivot, so at every run each element gets compared with the pivot. It has sublists which in one sublist gets items smaller than pivot and in the next sublist bigger than pivot, and then recombines sublists and pivot. The problem of this is to choose right pivot, and mostly for pivot is picked first or last item in the list. The time complexity of quick sort is different from previous three sorts. For partitioning list by pivot, and  halving problem size by 2 it overall takes O(nlgn). Quicksort is generally faster than other O(nlgn) algorithms. However, the worst case of using quick sort is using it on already sorted list because if it picks first element as pivot, it goes through the entire list. It's disaster. Hence, the time complexity will be O(n^2).
Mergesort, instead of choosing pivot, equally (mostly) halves the list. At every run, it halves into 2 sublists, recursively sorts, and recombines by repeatedly taking  the smallest element in he sublists.  Mergesort has O(nlgn) time complexity, and it's efficient on sorting a reversed sorted list compare to quick sort.
Timsort - the last but one of the most efficient sorting algorithm, and it's Python's built-in sort. The process of sorting of timsort is mix of existing sorting algorithms such as insertion and merge sort. The sorting performance of timsort on reversed, sorted, unsorted lists is quite impressive because it's faster than other sorting algorithms. Timsort can take O(n) time in the worst and best cases.