Multiple-input multiple-output (MIMO) is an essential technology for modern wireless communication systems. Spatial modulation (SM) is an evolving MIMO transmission scheme for energy-efficient massive MIMO systems. SM conveys the information of transmit antenna indices and modulated symbols in MIMO systems. A variant spatial permutation modulation (SPM) was further proposed to include transmit and time diversities by transmitting a permutation array of antenna indices during several time instants. The SPM achieves better error rate performance than the SM especially in fast fading channel. This paper investigates sphere decoding algorithms for the SPM receiver. An ordering scheme was proposed to reduce the number of visited nodes in the spherical tree search. The improved ordered sphere decoding saves about 95.6% computational complexity corresponding to 22.7 times throughput in the software implementation.