Quicksort with Trivalued Logic

What you have is not really a trivalued logic, but a partially ordered set (aka poset). There is a fairly large body of research on sorting partially ordered sets (a quick googling for "poset sorting" gives some good hits). In particular, you may want to look for something called a "chain merge data structure". Also, a paper called "Sorting and Selection in Posets".