>The old-style sort-merge join on map reduce requires both inputs to the join to be written to storage, shuffled across nodes and fully sorted even in the best case

It isn't full sort of both inputs. It sorts only what is on given node.