We propose to utilize the prediction-error of prediction error (PPE) of a pixel to reversibly carry the secret data in this letter. In the proposed method, the pixels to be embedded are firstly predicted with their neighboring pixels to obtain the prediction errors (PEs). By exploiting the PEs of the neighboring pixels, the prediction of the PEs of the pixels to be embedded can be then determined. And, a sorting technique based on the local complexity of a pixel is used to collect the PPEs to generate an ordered PPE sequence so that, smaller PPEs will be processed first for data embedding. By reversibly shifting the PPE histogram (PPEH) with optimized parameters, the pixels corresponding to the altered PPEH bins can be finally modified to carry the entire secret data. Experimental results have implied that, the proposed algorithm can benefit from the prediction procedure, sorting technique as well as parameters selection, and therefore outperform some state-of-The-Art works in terms of payload-distortion performance.