Sequential Monte Carlo (SMC) samplers are Bayesian inference methods to draw N random samples from challenging posterior distributions. Their simplicity and competitive accuracy make them popular in various applications of Machine Learning (ML), Bayesian Optimization (BO), and Statistics. In many applications, run-time is critical under strict accuracy requirements, making parallel computing essential. However, an efficient parallelization of SMC depends on how effectively its bottleneck, the redistribution step, is parallelized. This is hard due to workload imbalance across the cores, especially when the samples are of variable-size. A parallel redistribution for variable-size samples was recently proposed for Shared Memory (SM) architectures. This method resizes all samples to the size of the biggest sample, \(\overline{M}\) , and constrains the samples to be indivisible, i.e., forces the cores to redistribute whole samples. This leads to inefficient run-time, and a sub-optimal time complexity, \(O(\overline{M}\log _2N)\) . This study addresses the challenge of Optimal Parallel Redistribution (OPR) for variable-size samples. We first prove that OPR for indivisible variable-size samples is NP-complete. Then, we present an OPR algorithm for SM that does not resize the samples and allows cores to redistribute either whole samples or fractions of them. We prove theoretically that this approach achieves optimal \(O(\hat{M} \log _2 N)\) time complexity, where \(\hat{M}\) is the average size of the redistributed samples. We also show experimentally that the proposed approach is up to \(10\times \) faster than the reference method on a 32-core SM machine.