Order a list of points by closest distance

I wrote a function that will take a list of points and then order them so they sort of... "chain together".

The function will start with point #1 in the list.

It will add point #1 to the list of ordered by distance points.

It will then search for the closest point to point #1. (We'll call this point, point #2)

It will then add point #2 to the list of ordered by distance points.

And then... it will search for the closest point to point #2. (Which would be point #3)

You get the point.

The main problem with my code is: it's incredibly slow when dealing with lists that contain tons of points.

I would like some help optimizing my function to make it operate as fast as possible.

private static double Distance(Point p1, Point p2)
{
    return Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2));
}

private List OrderByDistance(List pointList)
{
    var orderedList = new List();

    var currentPoint = pointList[0];

    while (pointList.Count > 1)
    {
        orderedList.Add(currentPoint);
        pointList.RemoveAt(pointList.IndexOf(currentPoint));

        var closestPointIndex = 0;
        var closestDistance = double.MaxValue;

        for (var i = 0; i < pointList.Count; i++)
        {
            var distance = Distance(currentPoint, pointList[i]);
            if (distance < closestDistance)
            {
                closestPointIndex = i;
                closestDistance = distance;
            }
        }

        currentPoint = pointList[closestPointIndex];
    }

    // Add the last point.
    orderedList.Add(currentPoint);

    return orderedList;
}

I don't like any of these answers. In particular, the accepted answer is simply wrong.

Let's start by critiquing the interface:

List OrderByDistance(List pointList)

The contract is: the list must contain at least one element, the list is destroyed (!!!) by the method, the first element is special, and the result is a mutable list. I like nothing about any of this; this sounds like a ball of potential bugs. The right contract is:

ImmutableList OrderByDistance(Point start, ImmutableSet points)

Look at how many problems this solves. Do we need the set to contain at least one point? No. We already have the start point. Do we destroy the set of points? No. It's immutable. And so on.

Now that we have the signature correct, the algorithm is simple:

ImmutableList OrderByDistance(Point start, ImmutableSet points)
{
  var current = start;
  var remaining = points;
  var path = ImmutableList.Empty.Add(start);
  while(!remaining.IsEmpty)
  {
    var next = Closest(current, remaining);
    path = path.Add(next);
    remaining = remaining.Remove(next);
    current = next;
  }
  return path;
}

Now all you have to do is efficiently implement Closest, which you should be able to do given the previous hints about computing distances cheaply and so on.

If you want a more sophisticated algorithm for Closest, then you need to do some research on this well-studied problem:

https://en.wikipedia.org/wiki/Nearest_neighbor_search

StackExchange Code Review Q#139059, answer score: 9