Linear time algorithm to sort points of a simple polygon
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".