Published by Ron Graham in 1972, Graham's scan is an optimal algorithm for finding the convex hull of a set of points.
As a bit of historical curiosity, the original algorithm published by Graham was shown to be incorrect. It was:
Form a simple polygon from the input points going in counterclockwise order.
Find the point with the smallest y component.
Add this point and the point following it to the stack S.
While there are points left on the polygon,
while a right turn is formed by stack[top - 1], stack[top], and the polygon's next point,
pop the top point from the stack.
push the next point from the polygon onto the stack.
This doesn't work for all polygons though. In fact, it only works for those polygons which are weakly externally visible. So the obvious fix was to create the polygon in the first step that is guaranteed to be weakly externally visible. One easy method of doing this is to sort all the points according to the angle formed by the line between them and the point with the lowest y coordinate and a horizontal line coming from the point with the lowest y coordinate. Once this is taken care of, the stack always contains the convex hull of all the points seen so far at the end of the second while loop, so a loop-invariant argument for the correctness of the algorithm is straightforward.
Assuming that the method just given for creating a simple polygon is used, that takes O(n log n). The nested while loops would appear to take O(n2), but if you notice that no point can be popped off the stack twice, then it should be clear that it can take only O(n). Thus the time complexity is dominated by the O(n log n) sort.
The convex hull problem is Ω(n log n). For a proof, we reduce the sorting problem to it. For the sorting problem, we are given an array of numbers and we have to output them in sorted order. First we make all the numbers points of the form (x, x2) (an O(n) step). Then we find the convex hull of these points using any convex hull algorithm. Then we find the point in the output list with the smallest x coordinate and read off the x coordinates of the points in the order returned (another O(n) step). This gives us the input points in sorted order. Now if there was a convex hull algorithm faster than O(n log n), we would have a sorting algorithm that was faster than O(n log n). But we know that all sorting algorithms (in a comparison based model of course) are Ω(n log n), so that would not be possible.