The best you can hope for is $O(n \log n)$ plus a term dependent upon accuracy, for finding an approximate Euclidean MST. The fastest known exact algorithm is just a hair better than $O(n^2)$. Below is a central paper on the topic. Note especially: "The algorithm is deterministic and very simple."

Arya, Sunil, and David M. Mount. "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees." Proceedings 27th Annual ACM-SIAM Symposium Discrete Algorithms. SIAM, 2016. (PDF download.)

The best you can hope for is $O(n \log n)$ plus a term dependent upon accuracy, for finding an approximate Euclidean MST. The fastest known exact algorithm is just a hair better than quadratic, $O(n^2)$. Below is a central paper on the topic. Note especially: "The algorithm is deterministic and very simple."

Arya, Sunil, and David M. Mount. "A fast and simple algorithm for computing approximate Euclidean minimum spanning trees." Proceedings 27th Annual ACM-SIAM Symposium Discrete Algorithms. SIAM, 2016. (PDF download.)