Advanced Programming I Lecture Notes

2 February 2006 • Faster Sorting

static unsigned 
bits(int n, unsigned lsb, unsigned len) {

  // Return from n a block of len bits with with the least-significant bit of
  // the block being bit lsb in n (rightmost bit in n is lsb = 0).

  return (static_cast<unsigned>(n) >> rightmost) % (1 << len);
  }


static unsigned
ceiling(int a, int b) {

  // Return ceiling(a/b).

  return static_cast<int>(static_cast<double>(a)/b + 0.9);
  }


void
straight_radix_sort(int a[], unsigned n, unsigned radix_bits) {

  assert((0 < radix_bits) ∧ (radix_bits ≤ sizeof(int)*8));

  const unsigned radix = 1 << radix_bits;
  unsigned 
    * counts = new unsigned [radix],
    * starts = new unsigned [radix];
  int * tmp = new int [n];

  for (unsigned digit = 0; digit < ceiling(sizeof(int)*8, radix_bits); digit++) {
    unsigned i;

    memset(counts, 0, sizeof(unsigned)*radix);
    for (i = 0; i < n; i++)
      counts[bits(a[i], digit*radix_bits, radix_bits)]++;

    starts[0] = 0;
    for (i = 1; i < radix; i++)
      starts[i] = starts[i - 1] + counts[i - 1];
    assert(starts[radix - 1] + counts[radix - 1] == n);

    for (i = 0; i < n; i++)
      tmp[starts[bits(a[i], digit*radix_bits, radix_bits)]++] = a[i];

    memcpy(a, tmp, sizeof(int)*n);
    }

  delete [] counts;
  delete [] starts;
  delete [] tmp;
  }

This page last modified on 24 January 2006.