### Distribution-sensitive set multi-partitioning

*Amr Elmasry*

#### Abstract

Given a set

*S*with real-valued members, associated with each member one of two possible types; a multi-partitioning of*S*is a sequence of the members of*S*such that if x,y ∈*S*have different types and x<y, x precedes y in the multi-partitioning of*S*. We give two distribution-sensitive algorithms for the set multi-partitioning problem and a matching lower bound in the algebraic decision-tree model. One of the two algorithms can be made stable and can be implemented in place. We also give an output-sensitive algorithm for the problem.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page