Sorting and Efficiency

This is my entry on sorting and efficiency. Sorting refers to any type of algorithm/function that can be used to order the elements of a list or some other kind of data structure. We normally consider the efficiency of a sorting algorithm by how many calls the algorithm will make in the worst case scenario. The efficiency of different types of algorithms are categorized by "big Oh", for example O(n^2) would mean that in the worst case scenario the algorithm will have to make some constant multiplied by n^2 calls in order to sort n elements. Below are some of the main sort algorithms we have used specifically on lists and their efficiency.

Selection sort: Searches through the entire unsorted section of the list to find the smallest element, and moves it to the end of the sorted part of the list (efficiency is O(n^2))
Insertion sort: Sorts the list by moving the next element in the unsorted portion of the list to the appropriate place in the sorted part of the list (efficiency is O(n^2))
Bubble sort: Repeatedly searches through the entire list and swaps the position of adjacent elements that are not in the correct order (efficiency is O(n^2))
Merge sort: Recursively splits the list into halves, then sorts the halves and merges them back together (efficiency is O(nlog(n)))
Quicksort: Partitions the list into two halves where one half is smaller than the first element and the other half is greater than the first element, then puts the first element in between these two partitions and repeats the same process for the two partitioned lists (efficiency is O(nlog(n)))
We also talked briefly about python's built in sorting system list.sort(). This is the fastest of all sorting algorithms, but it is still of order O(nlog(n)) as this is the most efficient that it is possible for a sorting algorithm to be.