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.