Sorting Algorithms

There are many different types of sorting algorithms that can be coded in a program and each offer their advantages and disadvantages. Efficiency is a measure of how the running time of a program increases compared to the load given (n), for example as the size of a list increases.

First there is Selection Sort. This is a type of sorting method where the minimum value is selected and then switched to the first index, and then then next minimum is found and switched to the second index, etc. This sort is very inefficient once the lists grow because it does not cut down the running time because no matter what order the list is in even if it is partially sorted, it has to go through all the values. The efficiency of this sorting method is O(n^2).

Secondly there is Quick Sort. This is a type of sorting method where a divide and conquer approach is taken splitting up the list into smaller sections and then recursively working through the sub parts. A pivot point is picked at random and the elements are sorted to the left if it is smaller, and to the right if it is larger. This method is very efficient as the worst case is O(n^2), which is identical to the Selection Sort, however the best case is O(n log n), which is significantly faster!

Lastly there is Merge Sort. This is a type of sorting method where the list is broken down into single elements first and then sorted into groups of two (L[0] + L[1], L[2] + L[3], etc). After all the elements are sorted into groups of two, the groups are then sorted using the same method into groups of four, this keeps happening until there are only two lists left that are merged together into one. This method has a worst case of O(n log n), which is even faster then Quick Sort because it's best case is better then that (in the cases that the sub lists are already sorted).