Sorting and Efficiency

Sometimes, after returning a list of some kind from my code, I find myself wanting and/or needing to clean it up, so that it is properly ordered. In order to do this, I might employ the use of a sorting method, which will allow for me to sort the lists into the order of my choosing. There are many different types of sorts to choose from, that all work in different ways; bubble sort, selection sort, insertion sort, shell sort, merge sort, and quick sort. Bubble sort, as the name implies, works by "bubbling" an item in the list, and comparing it to an adjacent item, over and over again, until it finds its proper placement in the list. Selection sort works by selecting the largest item (in the unsorted part) in a list each pass, and then finding its proper location by the end of that single pass. Insertion sort works by essentially creating a sublist that starts with the first item of the unsorted list, that grows with each pass by placing the next item in the unsorted list into the sorted sublist in its proper order, and by the end, the sublist has become the new sorted list. Shell sort is essentially the same as insertion sort, but rather than using the entire list, it makes sublists, which are then sorted by insertion sort. Merge sort works by breaking a list down recursively into smaller and smaller parts, which are then compared, and reconstructed in the proper order into a new fully organized list. Finally, quick sort works by essentially choosing a point in a list at which the values pivot, meaning that the values around the pivot point will swap into the proper order, until the list has become properly sorted.

The different sorts take different amount of time to complete, depending on the type of sort and the length of the list that it is affecting. The way that the amount of time, or efficiency, is represented is by using the big-O notation, which will change depending on the length of n, which is the list. For example, insertion sort works in a O(n^2) run time, meaning that the run time grows proportionately with the length of the list squared. Another example would be merge sort, which works in a O(n log n) run time, which is just the O(log n) multiplied by the length of the list. Something of O(log n) has a run time that gets shorter and shorter for each iteration, and so O(n log n) would just be that multiplied by n. This is useful for larger lists, as it is capable of dealing with them with little difficulty, due to the shortening of run time, whereas something with O(n^2) run time will grow much larger and larger the bigger the list.