Sorting and Efficiency

The process of putting the items of a list in order is a straight-forwards enough task, but with enough required steps that it's pretty much the ideal task for an introduction to algorithm analysis with the multiple different possible implementations for each algorithm. We studied, edited and compared selection, insertion, bubble, quick, merge, count and  methods throughout the last several weeks of course material. Many of the algorithms had a worst case scenario in which the algorithm was significantly more inefficient than it was expected to be, generally when the list was either sorted or reverse sorted. This can be generally remedied by randomly rearranging the list beforehand. In the case of small lists were the worst case has a higher chance of appearing randomly the small list size should be processed in a fraction of a second regardless. For lists with hundreds or thousands of elements where the runtime really shows, the list randomly sorting into a significantly undesirable configuration is too unlikely to be problematic. Of course the scrambling itself would add a bit to the runtime, but oh well it all comes out in the wash.

Sorting methods that go over each element in succession generally have a sorting time of n^2 where n is the size of the list, as with each additional element it creates more possibilities for the relative position of all the other elements. Sorting methods that sort the elements between two or three large groups and in turn sorts those groups into smaller groups generally have a sorting time of  log(n), as loosely sorting the all the elements continuously will always be more efficient than picking and choosing between two individual elements.