We consider the minimax estimation problem of a discrete distribution with support size <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> measures the privacy level of a privatization scheme. For a given <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>, we consider the problem of constructing optimal privatization schemes with <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> is very close to 0, and in the low privacy regime where <inline-formula> <tex-math notation="LaTeX">$e^{\epsilon }\approx k$ </tex-math></inline-formula>, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when <inline-formula> <tex-math notation="LaTeX">$1\ll e^{\epsilon } \ll k$ </tex-math></inline-formula>. More concretely, we prove that when <inline-formula> <tex-math notation="LaTeX">$3.8 < \epsilon <\ln (k/9) $ </tex-math></inline-formula>, our schemes reduce the expected estimation loss by 50% under <inline-formula> <tex-math notation="LaTeX">$\ell _{2}^{2}$ </tex-math></inline-formula> metric and by 30% under <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> metric over the existing schemes. We also prove a lower bound for the region <inline-formula> <tex-math notation="LaTeX">$e^{\epsilon } \ll k$ </tex-math></inline-formula>, which implies that our schemes are order optimal in this regime.