There wouldn't be enough oxygen for any bacteria to decompose the body, right? Not to mention, the radiation of space might kill off most organisms on it. So would it decompose, given millions of years?
In these conditions, bodies mummify.
The microbes that live in you, wouldn't survive the freezing, dessication and radiation. There is no real upper limit on how long a mummified body could exist in space. There would be nothing to cause the body to change, and so it would remain. There would be a slow breaking down of surface proteins, due to UV light, and eventually micrometeorites would erode the body, but these processes would take many millions of years.
Mars is hot enough to keep a body unfrozen oxygen and moisture also speed up the decaying process. A dry environment and constant heat like a desert would mummify a person like beef jerky.If the moon is always under freezing and no air the body would be freeze dried and look like a wax version of themselves forever.