In order to measure larger volumes in magnetic particle imaging, it is necessary to divide the region of interest into several patches and measure those patches individually due to a limited size of the field of view. This procedure yields truncation artifacts at the patches boundaries during reconstruction. Applying a regularization which takes into account neighbourhood structures not only on one patch but across all patches can significantly reduce those artifacts. However, the current state-of-the-art reconstruction method using the Kaczmarz algorithm is limited to Tikhonov regularization. We thus propose to use the stochastic primal-dual hybrid gradient method to solve the multi-patch reconstruction task. Our experiments show that the quality of our reconstructions is significantly higher than those obtained by Tikhonov regularization and Kaczmarz method. Moreover, using our proposed method, a joint reconstruction considerably reduces the computational costs compared to multiple single-patch reconstructions. The algorithm proposed is thus competitive to the current state-of-the-art method not only regarding reconstruction quality but also concerning the computational effort.