Information on cluto high perfromance

I would like to know how cluto is performing so fast with large data sets. I have deveopled my own application for clustering based on I2 criterion function but for the huge data sets the performance degrades. Also i have used the sparse matrix based concept to reduce the memory usage.
I appreciate help over this .