To effectively solve the problem of low visual quality of stego-image in existing color image Reversible Data Hiding (RDH) algorithm, a novel RDH scheme based on multi-level interpolation prediction and global sorting is proposed. Firstly, to make full use of the features of different texture regions in the image, a multi-level interpolation prediction algorithm is designed to significantly improve the prediction accuracy of pixels. Then, a global sorting strategy based on complexity is designed to sort the prediction errors in the three channels of color images respectively, making full use of the global characteristics of the prediction errors in each channel. A more concentrated Three-Dimensional Prediction Error Histogram (3D PEH) is generated. Finally, the adaptive 3D mapping strategy is used to modify the error histogram and embed the secret data. Experimental results show that the proposed method achieves better embedding performance compared with the latest schemes.