  Sorting algorithms have attracted a great deal of attention and study, as
they have numerous applications to Mathematics, Computer Science and related
fields. In this thesis, we first deal with the mathematical analysis of the
Quicksort algorithm and its variants. Specifically, we study the time
complexity of the algorithm and we provide a complete demonstration of the
variance of the number of comparisons required, a known result but one whose
detailed proof is not easy to read out of the literature. We also examine
variants of Quicksort, where multiple pivots are chosen for the partitioning of
the array.
  The rest of this work is dedicated to the analysis of finding the true order
by further pairwise comparisons when a partial order compatible with the true
order is given in advance. We discuss a number of cases where the partially
ordered sets arise at random. To this end, we employ results from Graph and
Information Theory. Finally, we obtain an alternative bound on the number of
linear extensions when the partially ordered set arises from a random graph,
and discuss the possible application of Shellsort in merging chains.
