Carry the key
Never identify a result by where it landed. Put the key inside the value, and a changed finish order cannot mislabel anything.
Sort at the edge
Output that a person reads should be sorted. The work itself should not care about order at all, which is what makes it parallel.