Tips on speeding up hierarchical linkage clustering algorithm I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.
I read about this algorithm here.
These are the steps:

Compute distance matrix between all points (great-circle distance, not Euclidean)
Find the pair of points with the minimum distance between them
If the minimum distance is larger than a threshold value

the algorithm finishes


Otherwise

The two points are merged, and removed from the list of points.
The center point of this pair is added to the list of points


Go back to 1

I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).
It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.
Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.
Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?
I am using MATLAB R2018b.
Thank you!
Yes.  After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again.  That will be vastly faster.