Clarke and Wright’s savings algorithm (CW algorithm) is one of the most widely used heuristic methods for solving the capacitated vehicle routing problem (CVRP). Given a scenario with n customers and a depot, the CW algorithm initially generates n distinct delivery routes, each connecting a single customer to the depot. It then iteratively merges the two routes based on their saving values under the constraint that the total load of items delivered on the new route does not exceed the vehicle capacity. Herein, the saving value represents the distance reduction achieved merging two routes in to one by linking two customers from different routes. This involves generating \(n\times (n-1)/2\) saving values and sorting them in descending order in order to merge the routes with larger saving values preferentially. However, it leads to the overall time complexity of \(\mathcal O(n^2 \log n)\) when comparison-based sorting algorithms such as the merge sort are employed. In this paper, we propose a variant of the CW algorithm for solving large-scale Euclidean CVRPs achieving a best-case time complexity of \(\mathcal O(n^2)\) . Our proposed approach calculates the saving values using approximate Euclidean distances derived from only integer arithmetic, then sorts the obtained saving values by distribution-based sorting algorithms that can arrange integer values in linear time. Experimental results show that our proposed approach handles large-scale problems involving 3, 000 to 30, 000 customer nodes in \(2.88\) s on average while preserving the solution quality, which corresponds to \(6.0\times \) speedup over the original CW algorithm.