Indeed, a check whether an angle is less or more than PI can be done in constant time using determinants. This totals to O (N).
If all the angles have the same orientation, we should still check whether the polygon is also not self-intersecting. Here, it will suffice to add up all supplementary angles and check whether the sum is 2 * PI. It will be fine to use floating point and check for approximate equality. This is also O (N).
However, we should visit the vertices in the order they follow on the polygon border. If you are given a polygon, you perhaps have that order already. On the other hand, if you are given just a set of points on the plane, a polygon with vertices in these points is not unique in the general case. So, there is no need to sort the vertices by anything: not only it is O (N log N), but we also lose important order information by doing so.
We can start from any vertex.