I kind of stopped reading after I learned the algorithm requires O(sqrt(n)) blocks each of O(sqrt(n)) size. Since sqrt(n)*sqrt(n) = n, how is this an improvement over the standard technique that simply uses an additional O(n) space?
You misunderstand. The algorithm chunks the existing input into O(sqrt(n)) blocks of O(sqrt(n)) size. That's why they call it an "in place" merge.
I kind of stopped reading
Seldom is a comment beginning with this insightful. Why stop or "kinda stop", and then criticize? Only criticize if you have read FULLY.
Hint: "in place".
I deserved that. Thanks also to jemfinch for more constructively pointing out my error. It happens from time to time: one's mind gets stuck on a detail, in this case a misunderstanding, and starts rejecting, which kills learning dead in its tracks. This all swims in a sea of "half as fast" and "not order-preserving" which further reinforces rejection - after all, if one wanted a non order-preserving in-place sort, there are faster ones. None of this is in any way a criticism of the paper but more a reflection on the state of mind that leads sometimes to being less than insightful.