Sorting and Efficiency

During the last few weeks we learned about varies sorting methods and their running time. The methods that are new to me are count sort, quick sort and merge sort.I learned that the idea about quick sort is to choose pivots, and so the list is divided into two parts. Then use quick sort to move the objects smaller than pivot recursively to the left of the pivot, and larger object to the right. The run time of quick sort is O(n log n).

Merge sort keeps dividing the list by two and obtains n sublists, each contains one element. And it keeps merge the values into new sublists. Merge sort is one of the O(n log n) sorting algorithm and has a worst case run time of O(n logn). It's faster than quick sort's O（n^2). But it takes more space than quick sort. 

In the lab this week, we compared these two algorithms with selection sort, bubble sort, insertion sort and python's built in sort(tim sort). It turns out that those O(n log n) algorithms(quick sort, merge sort and python's built in sort) are significantly faster than other algorithms when dealing with large inputs. Quick sort is fast for best case and normal case, but is slower than the merge sort for the worst case. Python's built-in sort is the fastest in most of the tests.