Question :

You are required to sort a file containing integers between 0 and 999999.

You cannot afford to use one million pigeon-holes, so you decide instead to use one thousand pigeon-holes numbered from 0 to 999.

You begin the sort by putting each integer into the pigeon-hole corresponding to its first three figures.

Next you use insertion sorting one thousand times to sort the contents of each pigeon-hole separately, and finally you empty the pigeon-holes in order to obtain a completely sorted sequence.

Would you expect this technique to be faster, slower or the same as simply using insertion sorting on the whole sequence (a) on the average, and (b) in the worst case? Justify your answers.