Internet of Vehicles (IoV), a branch of Internet of Things utilized for vehicle-to-vehicle communication, is attracting attention from both academia and industry. Vehicle nodes are thought to be constantly moving at high speeds, and as a result, IoV faces major challenges, including scalability, rapid topology changes, and shortest routing path. Vehicle clustering is an effective way to enhance IoV communication performance in a large network setting with complicated road conditions and huge number of vehicles. At the same, minimal clusters and selection of stable cluster heads (CHs) reinforce the cluster structure stability. In this sight, we propose a new clustering algorithm based on the recent nature-inspired metaheuristic IoV clustering using sparrow search algorithm (IoVSSA). IoVSSA incorporates mobility metrics along the cluster distance to construct the fewest clusters with stable CHs. Through simulation studies, the effectiveness of the proposed IoVSSA algorithm is assessed and is found to perform better than the state-of-the-art algorithms when it comes to the number of vehicle clusters and average cluster lifetime. Factors, including the network grid size, average cluster lifespan, and node transmission range, are considered for optimal clustering and the experiments make use of a variety of scenarios to compare the effectiveness of each algorithm.