I would suggest:

• For each point, detect the closest point on the line,

• measure how far along the line this is, distance =d (max length of line =D)

• Detect whether the point is to the left (L) or the right (R) of the line (even though this is subjective at the 2 ends)

• combine these to give each point a side and distance combination Ld or Rd , eg L0, L0.2, R0, R3.3.... RD

• sort the points L0 to LD followed by RD to R0.

• There are likely to be multiple L0, R0, LD and RD points because multiple points are closest to the ends of the line. For these (and other tied points), introduce a tie-breaker which measures the angle (from tangent to the line) more precisely than just left and right.

This algorithm will work best if the points follow the line reasonably well

It will be poor if the points are uncorrelated with the line.