In this paper, we investigate the question of how a legged robot can walk efficiently by taking advantage of its ability to alter its gait as a function of statistical (large-scale) terrain properties. One of the contributions of this paper is the algorithm to achieve real-time terrain identification and autonomous gait adaptation on a legged robot. We approach this problem by first classifying the terrains based on their proprioceptive responses and identifying the terrain in realtime. Then we choose an optimal gait to best suit the identified terrain type. We exploit our recent findings regarding gaits, estimated from terrain-contact signatures, in order to obtain an optimized mapping between terrain signatures and terrainspecific gaits. We evaluate our algorithm on synthetic data, and real robot data collected on different terrains and naturally occurring terrain transitions. Another key contribution of this work is the statistical verification that precise gait selection can lead to energy savings in practice in legged robots. This assessment of energy efficiency, achieved by gait adaptation, is among the firsts of its kind in gait adaptation literature. We also present an analysis of the effect of terrain transition frequency on our gait adaptation algorithm. Our results are supported by validation using both synthetic data and field testing.