The sorting is dependent on some implementation details and additional functionality in Google's runtime. See section 4.2:
We guarantee that within a given partition, the intermediate
key/value pairs are processed in increasing key order. This ordering
guarantee makes it easy to generate a sorted output file per
partition, which is useful when the output file format needs to
support efficient random access lookups by key, or users of the output
find it convenient to have the data sorted.
The system also allows an arbitrary partitioning scheme (mentioned in section 4.1). The sorting system uses this scheme:
The partitioning function uses the initial bytes of the key to
segregate it into one of R pieces.
Thus when the Reduce function is run on each partition there are no changes to the data but the output is guaranteed to be in correct order (presumably there's nothing special about the implementation of this - it's just a simple local sort of some kind).
Once you have your sorted partitions, all you have to do then is concatenate them in the order of the initial bytes that were used to make the partitions and you have a fully sorted list.
(I'm taking a "sorting key" to be a summary of the value that's designed such then when the keys are sorted the values are also in the correct sorted order, at least to a reasonable approximation. Simply truncating the first letters of a string would be enough to make a crude sorting key)