How does sorting come into play with convex hull?

Question

I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull. From there on, I am confused. How could an algorithm like this get the other points of the hull?

Answer 1

It is easier to catch the connection with sorting if you first sort the points by their polar angle. This is the basic idea for the Graham scan. Though, the idea with sorting points by the x-coordinates also works: you need then to apply just a slight modification of the same Graham's algorithm).