Quick Sort If size <= 1, DONE. Choose a pivot. Split the array into two pieces, one piece <= pivot, the other piece >= pivot. Quick Sort both pieces. There are several different strategies for picking a pivot. (First element in array, randomly selected element in array, median of three randomly selected elements in the array.) Using messy math, this runs in THETA (n lg n) time on average, assuming any pivot is equally likely. Even if you get a bad pivot from time to time, the average is still n lg n. If the fact that the n lg n time is not mathematically guaranteed, use Merge Sort instead. Merge Sort is very fast and the n lg n time is guaranteed. The reason some people don't like Merge Sort, is that Merge Sort doesn't sort in place. You have to make a copy of the whole array...you don't have to do this in Quick Sort. You can also mess with the pivoting algorithm, the thing that separates the two lists. My biggest issue was dealing with ties in the array. What if there are values equal to the pivot? A bad pivoting algorithm will handle this poorly. My pivoting algorithm (when I was 13) put all the ties to the pivot in the second half of the array. So, if there were a lot of ties, the algorithm would run more slowly and if all the elements were the same, it becomes n^2 (or, if I program it especially poorly, infinite). Some algorithms put half of the ties into the first of the array and the other half into the second half. Quick Sort (in its basic form) does not offer stability. A stable sort is one in which if there ties in the input, the ties end up in the same relative order that they were in the original list. So, if you have three A's, then the A first in the unsorted list appears first in the sorted list as well, etc. Why would you want this? Why would you even care? In real life, your data contains information other than the specific thing you're sorting on, and it's the order of the other stuff that you want to preserve. Quick Sort does not preserve stability. Shell Sort does not preserve stability. I don't think Heap Sort does. Merge Sort does. And a lot of the stupid sorts do. Bubble Sort, Insertion Sort, they preserve stability. If you only compare adjacent items, it's easy to preserver stability. One way to preserve stability is to append a tag field to every element in the array. A N D R E W P O E 0 1 2 3 4 5 6 7 8 It doesn't matter which sort I use, making this stable is now easy. I have 2 e's: E4 and E8 and I can keep track of which from the tag field. (If your keys are unique, stable sorting is automatic.) When you talk about algorithms that require sorting as a component of the algorithm, no one really talks about exactly which sort you are using, since unless you're a moron, you are using some n lg n sort. How fast can sorting be? Not just one specific algorithm, but the best algorithm anyone could possibly think of? And the answer is a bit nuanced because you have to consider what is "allowed" in your sorting algorithm. When most people think of sorting, they are thinking "comparison-based sorting:" The only way you can tell whether one element comes before or after (or is equal to) another is to apply a direct comparison between the two. This is very generic. It doesn't matter what sort of data you're sorting, as long as you can compare one to another to learn which comes first. A comparison splits the number of available possibilities for the sorted list into two groups, those that can no longer be possible and those that are still possible. CAT: CAT CTA ACT ATC TAC TCA So, if I compare the C and the A some of the possibilities in the above list are no longer possible. Not possible: CAT CTA TCA Still possible: ACT ATC TAC compare the C and the T Not possible: ATC TAC Still possible: ACT So, if I have a list of n elements, there n! possibilities for the sorted list. If I'm so awesome, that I can split that list in half every single time by making a good choice for the elements I choose to compare, then after one compare, there n!/2 possibilities, after two compares, there are n!/4, then n!/8, then n!/16, etc. So, to get down to one element, would take lg (n!). n! = n(n-1)(n-2)(n-3)...1 lg (n!) = lg n + lg (n-1) + lg (n-2) + ... + lg (1). < lg n + lg n + lg n + ... + lg n = n lg n So, lg (n!) = O (n lg n). From the diagram, lg (n!) = OMEGA (n lg n). Therefore, lg (n!) = THETA (n lg n). Stirling's approximation: n! is about n^n e^-n sqrt (2 pi n) This tells us that if we are able to split our list of possible ordering in half every time, we still are not going to do better than n lg n. Now, this whole discussion is based on the notion that all we have to go on is the comparison function, that this is the only tool we have to put things in order. But, if this is not true, there are other, clever, sorting routines that can run, say, in THETA (n). Counting sort. For example, suppose you know that you are only going to be sorting integers from 0 to 99. You know for a fact, that this is the only data. If you have a million entries in your array, you know that they will only occur from 0 to 99. So, what would be a fast way to do this? Go through the array and keep a tally: Ct[A[i]]++ When I'm done, I have, say, 9,236 0's. 11,218 1's...and so forth. Then, just write in 9,236 0's. 11,218 1's. And done. THETA (n) to make the count. And THETA (n) to overwrite the array with the new stuff. Now, the problem with this is that this crude will sort the array of integers, but what if there's other data that goes along with the integers. Andrea's way: Create a number of arrays, one for each possible sort value, As you move through the array the first time, you copy over data into one of these arrays, and when you're done, copy them back. Along the line's if you interpret the array as linked list, it's not to connect the 37, say, to the last 37 you saw. And when you are done, you can link everything together at the end. 49855 <== array of ints from 0 to 9 Ct 0 1 2 3 4 5 6 7 8 9 0 0 0 0 1 2 0 0 1 1 Create a running sum by adding each entry to the previous in the array 0 0 0 0 1 3 3 3 4 5 5 digits are 9 or less 4 digits are 8 or less