In this paper, several techniques are proposed to reduce the complexity of sphere decoding of multiple-input multiple-output (MIMO) codes without compromising its near ML performance. We show that by appropriate re-ordering of the search dimensions, the MIMO detection complexity can be significantly reduced. A simple technique is also proposed to make the sphere decoding complexity less sensitive to the initial search radius. These approaches are also shown to provide significant reductions in the complexity of list sphere decoders, which can be deployed as soft-output MIMO decoders.