Phase Retrieval (PR) in X-ray Crystallography (XC) is an inverse problem that consists on recovering an image from phaseless data. Recently, it has been shown that an image in XC can be sparsely represented in the Fourier domain. This fact implies that the number of required measurements to retrieve the phase in XC is determined by the sparsity, which is much smaller than the size of the image. However, the computational complexity to retrieve the phase still depends on the image size, implying more time to solve this problem in XC. Therefore, this work proposes a reconstruction algorithm that exploits the sparsity of the image by grouping sets of pixels of its sparse representation, called super-pixels, in order to reduce the total number of unknowns in the inverse problem. The proposed recovery methodology leads to a reduction in time of at least 80% and improves the reconstruction quality in up to 6% in terms of the Structural Similarity Index Measure (SSIM) compared to state-of-art counterparts.