Three Partition Refinement Algorithms
Robert A. Paige, Robert Endre Tarjan · SIAM Journal on Computing · 1987
We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.