I need an algorithm to sort multiple lists of points in a 2D plane so that corresponding points each list have minimized distance between them.
i.e. for two lists of equal length, the first point of the first list has minimal distance to the first point of the second list, second point of first has minimal distance to the second point of the second, etc.
My first thought was to simply sort by the average of the x and y coordinates, but I feel like that is not entirely accurate.
If you are trying to minimize the total distances between adjacent points, this isn't a sorting task at all.
Instead, it seems like you are trying to solve a Hamiltonian Path problem in 2-dimensional space. This is NP-complete for arbitrary distances between points. Even the restriction to Euclidean distances, in your case, is still NP-complete, but there are approximation algorithms; see https://www.ads.tuwien.ac.at/teaching/ws10/AlgGraphen/ag3-2x2.pdf. In general, the Euclidean TSP can be approximated in polynomial time due the work of Sanjeev Arora, for which he won the Gödel Prize:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765
Search for Euclidean Traveling Salesman problem and you will also get links to other scientific papers discussing how to approximate a solution to this.