Sorting an array with minimal number of comparisons

Donald Knuth's The Art of Computer Programming, volume 3 has a section on exactly this topic. I don't have the books here with me, but I'm pretty sure Knuth presents the algorithm for 5 elements. As you suspect, there isn't a general algorithm that gives the minimal number of comparisons for many sizes, but there are a number of common tricks that are used in such algorithms.

From vague recollections, I reconstructed the algorithm for 5 elements, and it can be done in 7 comparisons. First, take two separate pairs, compare inside those, and compare the smaller ones of each pair. Then, compare the remaining one against the larger of these. This now splits into two cases according to whether the remaining element was smaller or larger, but in all cases it's possible to finish in the three comparisons still available.

I recommend drawing pictures to help you. Knuth's pictures are something like this:

   o---o
  /
 o---o

which shows the results after the first three comparisons (and from what I recall, this kind of a picture appears in many minimal-comparison sorts). A line connects two elements whose order we know. Having such pictures helps you in determining which elements to compare against, as you want to make a comparison that gives you the maximal amount of information.

Addendum: Since there is an accepted answer with actual code, I guess there's no harm in finishing up these diagrams, and they might be a useful addition to the answer. So, start with the above one, and compare the missing element against the one on the top left. If it is larger, this will lead to

    /--o
   o
  / \--o
 o
  \--o

Now, compare the two large elements at the top right and we end up with

   o---o---o
  /
 o---o

Now, by comparing the bottom right element first against the middle one on top and then against whichever side it belongs on, we place it correctly using the remaining two comparisons.

If the initial comparison resulted in the remaining element being smaller, the diagram becomes

 o---o---o
    /
   o---o

Now, compare the two that have yet nothing smaller than them. One option is the last diagram above, which is solvable with the remaining two comparisons. The other case is

       o---o
      /
 o---o---o

And here again, the one that is not yet in sequence with the others can be placed correctly with two comparisons.

Yes it is in Knuth vol 3 page 185 (section 5.3.1). This was first documented in a PhD thesis so your Prof is being quite hard on you! There is no really simple elegant method; you have to track it as a partially ordered tree.

Here it is in lisp. Tested OK (SBCL on Linux)

(defun small-sort (a)  
  "Sort a vector A of length 5"  
  (if (> (aref a 0) (aref a 1))  
      (rotatef (aref a 0) (aref a 1)))  
  (if (> (aref a 2) (aref a 3))  
      (rotatef (aref a 2) (aref a 3)))  
  (if (> (aref a 0) (aref a 2))  
      (progn  
        (rotatef (aref a 0) (aref a 2))  
        (rotatef (aref a 1) (aref a 3))))  
  (if (> (aref a 4) (aref a 2))  
      (if (> (aref a 4) (aref a 3))  
          (progn)  
          (rotatef (aref a 3) (aref a 4)))  
      (if (> (aref a 4) (aref a 0))  
          (rotatef (aref a 2) (aref a 4) (aref a 3))  
          (rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2))))  
  (if (> (aref a 1) (aref a 3))  
      (if (> (aref a 1) (aref a 4))  
          (rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4))  
          (rotatef (aref a 1) (aref a 2) (aref a 3)))  
      (if (> (aref a 1) (aref a 2))  
          (rotatef (aref a 1) (aref a 2))  
          (progn)))  
  a)  

(defun check-sorted (a)  
  (do ((i 0 (1+ i)))  
      ((>= i (1- (array-dimension a 0))))  
    ;;(format t "~S ~S~%" (aref a i) (aref a (+ 1 i)))  
    (assert (<= (aref a i) (aref a (+ 1 i))))))  

(defun rr ()  
  (dotimes (i 100000)  
    (let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0) ))))  
      ;;(format t "A=~S~%" a)  
      (let ((res (small-sort a)))  
        (check-sorted res)  
        ;;(format t "Res=~S~%" res)  
        ))))