[hofstee]

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.

[calinet6]

For sure. But that's a far more nuanced argument than "twice as fast." :)