Sonic 3K Development: Mushroom Hill and Sandopolis

Sonic 3 was developed in tandem with what became Sonic & Knuckles.
The original plan was to feature all content from Sonic & Knuckles in Sonic 3.
Ultimately, the content was divided between the two games.
As a result, zones were shuffled around; the most notable being Flying Battery.

Here is a map of Angel Island from Sonic 3K:

In this original configuration the zone order was as follows:
Angel Island
Hydrocity
Marble Garden
Carnival Night
Flying Battery
Ice Cap
Launch Base
Mushroom Hill
Sandopolis
Lava Reef
Hidden Palace
Sky Sanctuary
Death Egg

Sonic was to have launched up to Flying Battery from Carnival Night.
Then jump down from Flying Battery and surf down to Ice Cap on a door.
Launch Base always preceded Mushroom Hill.
With Flying Battery between Carnival Night and Ice Cap,
Sandopolis directly follows Mushroom Hill.

The shift in landscape there may seem odd, but I assure you it isn't!
Mushroom forests, acting as an oasis, have appeared within deserts before.
One prime example would be in Dragon Ball.
Emperor Pilaf's castle is situated in a desert that features sections full of fungus.
It should be noted that elements from Dragon Ball inspired elements of Sonic.
Perhaps most notably in the Super Sonic transformation, particularly in Sonic 2.

Also of note is that Mushroom Hill was once named Mushroom Valley.
Valley was likely changed to Hill when it became the starting zone for S&K.