[PERF/ENH] Series.map sorts a larger dataset than it needs to

[wence-]

Series.map which substitutes values in self that match some key with its corresponding value does:

            lhs = cudf.DataFrame({"x": self, "orig_order": arange(len(self))})
            rhs = cudf.DataFrame(
                {
                    "x": arg.keys(),
                    "s": arg.values(),
                    "bool": full(len(arg), True, dtype=self.dtype),
                }
            )
            res = lhs.merge(rhs, on="x", how="left").sort_values(
                by="orig_order"
            )
            result = res["s"]
            result.name = self.name
            result.index = self.index

So the order is the same as the input.

This has two pessimisations:

1. In pandas-compat mode (since Match pandas join ordering obligations in pandas-compatible mode #14428) this merge doesn't need sorting
2. Since we only return s, we can get away with sort_by_key of res["s"] rather than sorting a multi-column dataframe

[wence-]

cross-ref #6724