Could this issue be fixed in marshal itself? Off the top of my head, one possible option could be to use the marshalled bytes of each elements as a sort key, rather than the elements themselves. So serialize, *then* sort?