The question is to show how to sort n integers in the range of 0 ton 2 -1 in O(n

Question

The question is to show how to sort n integers in the range of 0 ton2-1 in O(n) time.
I'm not finding the solution to be very helpful. Here'swhy:

I need to understand the logic. Say we have n=4. Our possiblevalues are 16-1=15. This is a 2 digit number. The solution statesthat each digit ranges from 0 to n-1 which is 0 to 3. How does thissort anything above 4?
I'm not finding the solution to be very helpful. Here'swhy:

I need to understand the logic. Say we have n=4. Our possiblevalues are 16-1=15. This is a 2 digit number. The solution statesthat each digit ranges from 0 to n-1 which is 0 to 3. How does thissort anything above 4?
I need to understand the logic. Say we have n=4. Our possiblevalues are 16-1=15. This is a 2 digit number. The solution statesthat each digit ranges from 0 to n-1 which is 0 to 3. How does thissort anything above 4?

Explanation / Answer

Yes, this is possible using Radix Sort.
To understand, you need to know that Radix Sort takes time(d(n+k)) from 0 to k. In the case of your problem k is (n-1)since each digit is in the range of 0 to n-1. Next, transform allof your integers into 2 digit numbers (e.g. 2=02, 16=16, etc). Now,d=2.
Radix can sort the new numbers inO(2(n+(n-1)))=O(2(n+n))=O(2(2n))=O(4n)=O(n) ...linear time.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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