Linear time algorithm to sort points of a simple polygon In triangulating a simple polygon, using the concept of sweep line helper vertices etc, the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices). I'm trying to work out why... Assume there's no degenerate case (for any pair of points belonging to the polygon their $y$ coordinates are different). Because of such property a strict order exists $y_1&lt;y_2&lt;\ldots&lt;y_n$, assume each point is stored in floating point $y_i = (e_i,m_i)$, I can't really see how to sort these points in linear time... could anyone give me an hint?

Source :
Computational Geometry - Algorithm and application (DeBerg et all) chapter 3:

The claim is this


  We now analyze the running time of the algorithm. Constructing the
  priority queue $\mathcal{Q}$ takes linear time...


Any kind of priority involves order relationships, so I assume some kind of ordering algorithm is used. Eventually the priority queue can be implemented using binary trees or heaps (basically these are the same thing) but It would still require $O(n \log n)$. I know ordering algorithms that run in linear time, however I don't think any of those can be applied in case of floating point numbers.
You ask:


  the very first step is sorting the vertices of such polygon.
  Apparently this very step can be done in $O(n)$


but the book says


  We now analyze the running time of the algorithm. Constructing the priority queue QQ takes linear time...


Constructing a priority queue does not take as much time as sorting. Priority queues can be constructed in linear time. The most famous algorithm for doing this is called "heapify".