The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem with significant practical and theoretical importance. This paper focuses on the cycle merging algorithm, which constructs a Hamiltonian cycle by iteratively merging cycles from an initial assignment. To address the growing computational demands of large-scale TSP instances, we propose a parallelized implementation of this algorithm. Our parallelization strategy employs fine-grained load balancing, combining OpenMP for edge replacement evaluation and MPI for distributing tasks across processes. Key optimizations—including dynamic scheduling and thread-safe updates—enhance performance. Experimental results demonstrate significant reductions in execution time for instances with up to 3000 vertices, underscoring the effectiveness of parallelization in accelerating the cycle merging algorithm.