Some people say that the legume we call a "lentil" is
lens-shaped. Actually it's the other way around. For
thousands of years before optical lenses were invented,
the Latin name for the legume has been _lens, lentis_
(3rd declension f). http://en.wiktionary.org/wiki/lens#Latin
It seems to me that the highway mirage is a straightforward
example of a graded-index lens. The air in this situation
can be replaced by a cylindrical glass lens, with constant
(non-graded) index, if we make the lower part of the lens
thinner, so the bottom part has a V-shaped cross-section.
Graded-index version constant-index version
(air) (glass)
less index <--> thinner glass
==============
You can perfectly well have total internal reflection in
a graded-index medium with a smooth index profile; no
steps are required. Optical fibers (e.g. transatlantic
communication fibers) rely on this. http://en.wikipedia.org/wiki/Graded-index_fiber
(Step-index fibers exist also, but they are less common.)