Improvement of mutual information algorithm is good for gaining time delay in phase space reconstrution of time series rapidly and reliably. Firstly, fault of Cellucci’s mutual information algorithm is analyzed based on respectively partitioning plane, which constructed by a pair of Lorenz series with the same size, into four and sixteen grids with equal distribution probability in elements on each axis. Then improved mutual information algorithms is promoted based on the original probability matrix that shows the distribution of points corresponding to data pairs of Lorenz series on the plane by sorting two series respectively, replacing each numerical value with its order number in its own series so as to judge the element in which data sets are located and revising the last column and row of the matrix. Finally, after reconstructing phase space with the optimal time delay, comparison between the maximal Lyapunov exponent calculated by Rosenstein’s algorithm from time series and that gained by Jaccobi matrix from Lorenz equation is used to confirm the validity of the new mutual information algorithms. The results show that Cellucci’s mutual information algorithm will lead to wrong optimal time delay when series size is not a multiple of elements. The new algorithm, whose result is steadier when large numbers of data pairs are used, can not only eliminate the default of Cellucci’s algorithm but also is faster than Fraser’s algorithm. Besides, the lesser error of the maximal Lyapunov exponents from the comparison shows that the new mutual information algorithm is available and feasible.