- This paper presents a randomized algorithm for routing any permutation of N (log N)-bit messages on an N-node hypercube in O(log N) bit steps. Previous algorithms required at least Omega(log^2 N) bit steps. The algorithm is adaptive, and we show that any O(log N)-bit-step algorithm must be adaptive by generalizing the Borodin-Hopcroft lower bound on oblivous routing. In particular, we show that any randomized oblivious algorithm on a polylogarithmic-degree network requires at least Omega(log^2 N/loglog N) bit steps, with high probability, for almost all permutations.