A new version of Godunov scheme is proposed in order to compute solutions of a traffic flow model with phase transitions. The scheme is based on a modified averaging strategy and a sampling procedure. Several numerical tests are shown to prove the validity of the method. The convergence of the algorithm is demonstrated numerically. We also give a higher order extension of the method in space and time.