A better solution which only uses local connections between adjacent cells is Odd-Even Transposition Sort. When the cells are arranged in a 2D grid, Shearsort

A better solution which only uses local connections between adjacent cells is Odd-Even Transposition Sort. When the cells are arranged in a 2D grid, Shearsort sorts all the values in snake-like order in O(sqrt(n) log(n)). A slightly more complicated algorithm based on Shearsort is that of Schnorr and Shamir, which runs in O(sqrt(n)).