I've got this sorted! Sort of...

In this post, I am going to talk about different sorting algorithms and compare their effiencency using Big-O notation. Big-O classifies algorithms according to how their processing time changes (or use of space)to changes in input size.

We learned about three different sorting algorithms, selections sort, quick sort, and merge sort.

In selection sort you iterate through a given list looking for the minimum element and place that element at the first position. You do this again and place the next minimum next to the previous until you reach the end of the list. Since you need go through list of len n to find the min element and do this n-1 times, the Big-O of selction sort is O(n^2).

 For example, given a list L = [4, 3, 1] the first minimum of the list would be 1. That would be place at L[0] to give [1,4, 3] . The next search will be in the remaining unsorted part of the list. The mimimum of 3 will be placed st L[1] to give the final sorted list of [1,3,7].


Quick sort can be implimented using recursion. It involves by choosing an item in the list as a pivot point and reording the list around that point much like how items are ordered in a binary search tree. Items creater that the pivot item go to the right and items less than to the left. After the first recursive call, a new pivot point is chosen on point side and the process is repeated. This occurs until the list is sorted.  Its Big-O is O(nlogn) like a binary search tree.

Merge sort can also be implemented recursively. This algorithm invloves splitting the list in half  until it is a single element list and sorted the list. Its Big-O is O(nlogn) as well.

There are cases when merge sort will be more efficient than quick sort(and vice versa!) In very rare cases , quick sorts BigO is O(n^2).due to the pivot positon. If the the pivot chosen is always the next smallest element, it becomes equivalent to Insertion sort.

Any more insight into why merge or quick sort is more efficienct in certain cases?