Let’s do an example…

Java Implementation

  private static void radixSort(int[] numbers, int radix) {
     ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
     
     for (int i = 0; i < radix; i++) {
        buckets.add(new ArrayList<Integer>());
     }
     
     int copyBackIndex = 0;
     
     int maxDigits = radixGetMaxLength(numbers, radix);
     
     int pow = 1;
     for (int digitIndex = 0; digitIndex < maxDigits; digitIndex++) {
        for (int num : numbers) {
           int bucketIndex = (Math.abs(num) / pow) % radix;
           buckets.get(bucketIndex).add(num);
        }
        
        // Copy buckets back into numbers array
        copyBackIndex = 0;
        for (int i = 0; i < radix; i++) {
           ArrayList<Integer> bucket = buckets.get(i);
           
           for (int val:  bucket) {
              numbers[copyBackIndex] = val;
              copyBackIndex++;
           }
           
           bucket.clear();
        }
        
        pow *= radix;
     }
  }

What is the run time of this algorithm?

Let’s Look At Some Timing Examples…

Radix Sort… Lessons Learned

• It is misleading to describe radix sort as a \(\Theta(n)\) sort.
• More accurate to describe it as \(\Theta(dn)\), where \(d\) is the number of digits.
• If all of the keys are distinct, \(d = \log_{r} n\), where \(r\) is the radix.
• Radix sort only applies to some data types, and even then it only has a speed advantage under particular circumstances.

Lower Bound on Comparison-Based Sorts

• We won’t look at the proof, but it can be shown that any correct comparison-based sort (does not include radix sort!) requires \[\Omega(n\log n)\] comparisons in both the worst and average case.