Linear complexity in External Memory

In the standard RAM model, one hits the sorting bottleneck of \Omega(n\log n) sometimes, and researchers find ways around by using say word operations that avoid comparisons. In the PRAM world, people tried to get around certain sorting bottleneck by "padded sorting", where items can appear in sorted order but with empty memory locations between them.

I was recently drawn to this issue when working with Gianni Franceschini and Roberto Grossi. Consider the external memory (just the vanilla version with input of size N on disk, internal memory of size M, and block size B) model. Even problems like permuting an array that takes O(N) time in the RAM model, and therefore, should ideally just take linear number O(N/B) of block accesses, seem to take essentially \Omega(N/B \log_{M/B} N/B) block accesses in the external memory model; sorting, convex hulls, MST and other problems then face similar bottleneck.

I think this is fundamental and one would think researchers would have by now figured out different ways to circumvent this bottleneck with additional assumptions on the input or on the model. But I haven't found anything. Any pointers?

ps: Btw, for the problem we were working on, we did find an algorithm with linear number O(N/B) of accesses. The algorithm is too long to be described in this blog.