Code-based cryptography is based on the difficulty of the syndrome decoding problem (SDP) and is one of the promising candidates for post-quantum cryptography. Information set decoding (ISD) is known as one of the most efficient frameworks for solving SDP. There has been some work analyzing the time complexity of ISD in the situation where the amount of memory consumption is limited. In this work, we propose a new variant of the Both-May algorithm which is known as the fastest ISD. The proposed algorithm achieves more efficient asymptotic time-memory trade-offs compared with the original Both-May algorithm and existing time-memory trade-off versions of other ISDs.