Minimum spanning tree, minimize sum of point distances

I have 10^6 points in 2D. Every point has to be connected, and I should minimize the sum of those distances (between points). My algorithm is this:

1. Make a dict 'Visited', that marks if the point is visited.
2. Find the closest point to all 10^6 points.
3. Then sort array of 10^6 points by a distance of a closest point.
4. Then for loop(1000000):(all points!) if p1 is not visited, connect it to the closest point

When I sort array by distance reversed, I get a different answer. How is this possible, and how should I optimize this?

for i in range(1000000):
    x1, y1 = arr[i][0], arr[i][1]
    x2, y2 = arr[i][2], arr[i][3]

    if (x1,y1) not in visited:
        visited[(x1,y1)] +=1
        visited[(x2,y2)] +=1

        xs = (x1 + x2) / 2
        ys = (y1 + y2) / 2


        mid_point[(xs,ys)] = [(x1,y1), (x2,y2)]

I calculate radius (half distance*half distance*PI, not so important in this case, because r*r is also linear)