The Ckmeans.1d.dp algorithm clusters 1-D data given by a numeric vector x into k groups by dynamic programming (Wang and Song, 2011). It guarantees the optimality of clustering – the total of within-cluster sum of squares is always the minimum given the number of clusters. In contrast, heuristic k-means algorithms may be non-optimal or inconsistent from run to run. Apart from sorting in log-linear time, clustering contributes only linear in number of clusters and log-linear in sample size, comparable to heuristic k-means when no-restart is allowed. It is practical for Ckmeans.1d.dp to cluster millions of sample points within seconds using a single processor on a recent desktop computer.
providing 
.