Update 2026-07-03: when I wrote this post in 2019, I was convinced that scipy’s hierarchical clustering was too slow, and that the fastcluster package provided a speedup. I ended up using fastcluster throughout my PhD as I developed ARG-Needle up to its 2023 release (see here for instance).

However, it appears that scipy already shipped the nearest-neighbor chain algorithm for \(O(N^2)\) clustering in version 0.18.0, which was released July 25, 2016 on PyPI. Credit goes to Nikolay Mayorov for the scipy pull request, who credits fastcluster for inspiration. So my claim that scipy was stuck at \(O(N^3)\) runtime was inaccurate—either I didn’t verify the scaling myself, or I was using an older scipy version.

It’s possible that fastcluster is still the faster implementation than scipy by a constant factor. It looks like well-written C++ code; incidentally Daniel Müllner is still maintaining the GitHub repo as of 2026! Mayorov’s pull request is .py / .pyx.

Original post with outdated information crossed out:

Do you use hierarchical clustering packages like R’s hclust or Python’s scipy.cluster.hierarchy.linkage in your workflow? If so, you’re using an \(O(N^3)\) algorithm¹ and should switch to the fastcluster package, which provides \(O(N^2)\) routines for the most commonly used types of clustering.

fastcluster is implemented in C++, with interfaces for C++, R, and Python. In particular, the Python interface mirrors scipy.cluster.hierarchy.linkage, and the R interface mirrors stats::hclust and flashClust::flashClust, so switching over is a no-brainer.

For a performance comparison provided by the package’s author, take a look here. fastcluster is described in a Journal of Statistical Software publication from 2013, with algorithmic details in a 2011 arXiv paper. The key algorithms used to get to \(O(N^2)\) are a variant of Prim’s algorithm for minimum spanning trees and the nearest-neighbor chain algorithm. Note that centroid and median linkage still take \(O(N^3)\) time with this package.

I haven’t read the details of these algorithms yet, but if they are correct, then the Wikipedia articles on hierarchical clustering and UPGMA (average linkage clustering) could use an update².

Update 2026-07-03: Try and clear things up.