Sorting in Lattices

In a totally ordered set the notion of sorting a finite sequence is defined through a suitable permutation of the sequence’s indices. In this paper we prove a simple formula that explicitly describes how the elements of a se-quence are related to those of its sorted counterpart. As this formula relies only on the minimum and maximum functions we use it to define the no-tion of sorting for lattices. A major difference of sorting in lattices is that it does not guarantee that sequence elements are only rearranged. How-ever, we can show that other fundamental properties that are associated with sorting are preserved.