Bucket Sort

Single-digit Bucket Sort:

• stable: equal items stay in original order
• Run-time: $\Theta (n+R)$, auxiliary space $\Theta (n+R)$
• Bucket size is $R$ for array $B$.?

Warning

Don’t forget: if they say $R=2$ that means we are in base 2, binary.

Related

• LSD-Radix Sort
• MSD-Radix Sort

Questions

• The auxiliary space of BucketSort are both $\Theta (n+R)$. Why does this depend on $R$ in addition to $n$?
  • We initialize an array of buckets ($R$) in total storing them is $O(R)$.
• Run-time of Bucket Sort and LSD-Radix Sort the same?
  • No, in my opinion, LSD is faster? according to an assignment we did.
  • Bucket Sort has run time of $\Theta (n+R)$
  • LSD Radix Sort has a run-time of $O(m(n+R))$
• Given an array of integers $n$ where each entry is in the range $[0,2^n-1]$, the runtime to sort the array using BucketSort is in
  • $\Theta (n)$? no idea
  • Correct answer is $\Theta (2^n)$
  • Since we need $2^n$ buckets to cover all possible values.