There is a sorting network called AKS which has O(log(n)) depth. Batcher's Odd-Even Mergesort has a depth of O(log^2(n)). Which is better? In all cases where y

There is a sorting network called AKS which has O(log(n)) depth. Batcher's Odd-Even Mergesort has a depth of O(log^2(n)). Which is better? In all cases where you can fit n in the total memory capacity of the earth, Batcher's network is vastly superior. Constants matter a whole lot more than you might think. I'm not arguing against revising algorithms to look for better complexity classes, but if you rewrite your algorithm in a smaller complexity class you had better be sure that your constants are of reasonable size.