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

Question

You are required to sort a file containing integers between 0 and 999 999. You cannot afford to use one million pigeon-holes, so you decide to use one thousand pigeon-hole numbered from 0 to 999. You begin the sort by putting each 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.

Explanation / Answer

Solution:

The technique which is explained above is actually prove to be faster compared to simply sorting the 1 million elements. Actually average case performance and worst case performance is same in insertion sort. But the question is how using 1000 pigeon hole and sorting them individually will make the algorithm works faster. Since we have the value of n= 1000000, so if we sort 1000000 elements simply using insertion sort the algorithm will take O(n^2) which means (10^6)^2= 10^12.

Now considering 1000 pigeon holes containing 1000 elements each, so for a pigeon hole it will take O(n^2), which is (10^3)^2= 10^6, and for 1000 pigeon holes (10^6)*(10^3)= 10^9, which is very less compared to the previous 10^12.

After all the pigeon holes are sorted which are assigned by their first three digits so merging them will take constant amount of time.

I hope this helps. Don't forget to give a thumbs up if you like this.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.