Doggy Sort

A large group of dogs have their collars removed before they enter a dog facility. Except for their sizes, the collars are indistinguishable. When they exit the facility they will all need their collars back. Your task is to assign every dog to their corresponding collar. The catch is that you are not able to compare collar to collar or dog to dog. You can only compare a dog to a collar and see if it is too small, too big or if it fits. You want to minimize the comparisons you make. The best way of solving this problem requires a modification of one of the following sorting algorithms. Which one is it?