bubble sort

Worst: O(n^2)

A pretty terrible algorithm, but a really simple one to understand. Take the first two items, compare them, and swap them if needed. Then take the second and third items and compare and possibly swap those. Repeat to the end of the list. This first iteration will have only moved the largest item to the end of the list. Now you need to repeat the whole process again and again until you make it through the list without needing to swap anything.

insertion sort

Worst: O(n^2)

A bit more clever, check and swap the first two as with bubble sort, then the 2nd and 3rd, but then check the first two again. Basically, for each item you check the ones before it, moving it the whole way to the front if needed.

If you're got a hand of cards and you're putting them in order this is what most people tend to do. Although it's usually faster than bubble sort it's still O(n^2).

quick sort

Worst: O(n^2)

Pick a pivot point, an item in the middle of the list, then go through the list putting anything smaller than the pivot to its left and anything larger to its right. Then look at only the ones to the left and do the same process. Then you go through and do the same thing to the right side. The worst case is still O(n^2), but the average performance of a random list is O(n log n).

bogo sort

Worst: `O((n+1)!)

Designed as a joke or demonstation of O(n!). Just randomize the list. If it's sorted, done! Otherwise randomize it again.