I have the following coordinates for a line OR potentially non-convex polygon:

Rules:

1. each coordinate is at MOST 1 x or 1 y distance away
2. the coordinates WILL form a line with two end coordinates OR a fully connected loop (a polygon)

These coordinates come in a potentially random order. Ex:

5,3
3,4
4,4
6,4
2,5
6,5
2,6
5,6
3,6

I would like these sorted into a list, starting at one end, ending at another. It doesn’t matter if it’s clockwise or counterclockwise

Ex:
3,7
2,6
2,5
3,4
4,4
5,3
6,4
6,5
5,6

I could start at a random point, then search for an adjacent neighbour (since I know they’re at most 1,1 away), but this solution is O(n2) and computationally complex

I know for a concave polygon, you can sort by using angle from atan from an internal point, but if the lines connect it may form a convex polygon.