Sorting Algorithms

There's only two reasons to sort a list:

1. So that you can present it in a way that's more readable. Say, a list of state names in alphabetical order.

2. Increase the efficiency of things you do to that list. For example, retrieving and removing the max value element in the list over and over (for some reason...) 

There's a lot of ways to achieve both of those goals. And they all force you to understand the property of the list you want to sort and the characteristics of the sorting algorithm you use. 

• How much data are you trying to sort? 
• Is that data partially sorted?
• Can all that data fit in memory? 
• Does the algorithm you use maintain the relative position of equal values? (stability) 
• Does the algorithm require extra memory?

If you're a programmer, you should at least know the basic properties of some of the most common sorting algorithms such as ...

• Bubble sort (O(n^2))
• Go through the list looking at pairs of elements. If the left one is less than the right, swap their positions.
• Selection sort (O(n^2))
• Start at the first element. Now find the minimum and swap the minimum with the first element and then move on to the second element and find the minimum from the second element to the last and swap. 
• Insertion sort (O(n^2))
• Start at the second element and check if it's smaller than the first. If so, insert it before the first (the first becomes the second). You now have a partially sorted list! Now, you move on to the third element and insert it in the right position in that partially sorted list and continue until you have a fully sorted list.  
• Quick sort  (O(n log n))
• Pick a pivot and swap the elements so that all the numbers smaller than or equal to the pivot is on the left and those larger are on the right. Do this recursively!
• Merge sort (O(n log n))
• Split the list into individual elements, then merge them together (first by pairs) in order. The merge algorithm works by creating a new list and inserting the correct elements into the lists through comparisons of the two lists. 

Most general purpose languages include sorting functions in their core libraries so you shouldn't ever have to write one yourself :)