Viewers is more than 500000 per month. Which Hosting type will be good?

I know this is not coding problem but it is related with Web development. I am a freelancer from India, I am redesigning and redeveloping a Website for one of my client. The present website has more that 500000 viewers per month. And site performance was quite sluggish. And it was down for 1 and half months [almost]. So, I am quite confused where to host the new website. Which hosting type will be better? Shared hosting or VPS?

Thanks in advance..