Sorting is one of the most fundamental non-numeric algorithms which are needed in a multitude of applications. For example, map-reduce based computations in every step have to group the data items by key values. Or load balancing in supercomputers often uses space-filling curves. This boils down to sorting data by their position on the curve. To obtain sorting algorithms that scale to the largest available machines, conventional parallel sorting algorithms cannot be used since they either have prohibitive communication volume or prohibitive critical path length for computation. The authors outline ideas how to combine a number of basic algorithmic techniques which overcome these bottlenecks.