MSD-Radix Sort

Time Complexity

Best Case: $\Theta (n)$ Worst Case:todo

Questions

• What is the auxiliary space of MSD Radix Sort? ($m=$ number of digits, $n$: number of items that we wish to sort, $R$: radix (base) we are using)
  • $O(m+n+R)$ and not $(O(mn))$ in my mind, we need arrays of our original size $n$ the number of digits we have. So $n\ast m$ .

Related

• LSD-Radix Sort
• Bucket Sort