Recursive Sorting in Lattices

Abstract: The direct application of the definition of sorting in lattices is impractical because it leads to an algorithm with exponential complexity. In this paper we present for distributive lattices a recursive formulation to compute the sort of a sequence. This alternative formulation is inspired by the identity that underlies Pascal's triangle. It provides quadratic complexity and is in fact a generalization of insertion sort for lattices.

This page was built for publication: Recursive Sorting in Lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6242328)