Sorting Exactly Three Items

When doing QuickSort it's often fastest to switch to a simpler sort for the smaller array size stage. The following is pseudocode for sorting into ascending order the values in (size-compatible) variables p,q and r (which may be array elements) without unneeded moves or comparisons. Equal values are not swapped. The variable t is used to hold a value from p, q or r.

 if q < p
 {
    t = p;
    if r < q { p = r; r = t; }
    else
    {
       if r < t { p = q; q = r; r = t; }
       else     { p = q; q = t; }
    }
 }
 else
 {
    if r < q
    {
       t = r; r = q;
       if t < p { q = p; p = t; }
       else     { q = t; }
    }
 }

The code should be near-optimal (except in special situations) if used with an optimizing compiler, especially if t can be a register. One can proceed similarly for more values - stopping before too much memory is required for the code - and then choose to use it within other algorithms (e.g., QuickSort, MergeSort) which need to sort progressively fewer values.

---

SortingFewItems? can be done with the optimal number of comparisons. Known solutions exist for up to 6 items (I think). TheArtOfComputerProgramming gives more details.