In http://www.youtube.com/watch?v=k4RRi_ntQc8, Schmidt asks Obama "What is the most efficient way to sort a million 32-bit integers?". After doing some research (and getting some clues from the youtube comments), it appears that this can be achieved in O(n) time using a non-comparison-based sort. I decided to implement a radix sort as a proof of…

radixsort.c

#include <stdio.h>
#include <stdlib.h>

struct Numlist {
  // size of the list
  unsigned long size;
  // the array of integers
  unsigned int *arr;
};

struct ListInt {
  unsigned int val;
  struct ListInt *next;
};

struct Numlist getNumbersFromFile(FILE *fh) {
  struct Numlist nums;
  // initially allocate an array of size 1000. when we need more space,
  // reallocate with double the size so that we have a logarithmic number of
  // resizes required with respect to the input size.
  int capacity = 1000;
  nums.arr = malloc(sizeof(int) * capacity);
  nums.size = 0;

  int innum;
  // grab input from stdio, one int per line
  for (fscanf(fh, "%i", &innum); !feof(fh); fscanf(fh, "%i", &innum)) {
    if (nums.size >= capacity) {
      capacity = capacity * 2;
      nums.arr = realloc(nums.arr, sizeof(unsigned int) * capacity);
    }
    nums.arr[nums.size++] = innum;
  }

  return nums;
}

struct Numlist radix(struct Numlist nums) {
  // Take two passes over the numbers to sort them by their least significant
  // 16 bits, and then their most significant 16 bits.
  struct ListInt* buckets[1<<16] = {0};
  int i;
  for (i = 0; i < nums.size; i++) {
    unsigned int part = nums.arr[i] & 0x0000FFFF;
    // allocate a new ListInt
    struct ListInt *li = malloc(sizeof(struct ListInt));
    li->val = nums.arr[i];
    li->next = buckets[part];
    buckets[part] = li;
  }

  // now each bucket is in reverse order of insertion.  so populate nums backwards
  int n = nums.size;
  for (i = (1<<16)-1; i >= 0; i--) {
    struct ListInt *li;
    for (li = buckets[i]; li != NULL; li = li->next) {
      nums.arr[--n] = li->val;
    }
  }

  // now zero out our buckets array for the 2nd pass
  for (i = 0; i < 1<<16; i++) {
    buckets[i] = NULL;
  }

  // take a 2nd pass, based on most significant 16 bits
  for (i = 0; i < nums.size; i++) {
    unsigned int part = (nums.arr[i] & 0xFFFF0000) >> 16;
    // allocate a new ListInt
    struct ListInt *li = malloc(sizeof(struct ListInt));
    li->val = nums.arr[i];
    li->next = buckets[part];
    buckets[part] = li;
  }

  // same as above, populate the final nums array backwards from the bucket list
  n = nums.size;
  for (i = (1<<16)-1; i >= 0; i--) {
    struct ListInt *li;
    for (li = buckets[i]; li != NULL; li = li->next) {
      nums.arr[--n] = li->val;
    }
  }
}

int main(int argc, char **argv) {
  if (argc < 2) {
    printf("Usage: radixsort <file>\n");
    exit(1);
  }

  FILE *fh;
  if (!(fh = fopen(argv[1], "r"))) {
    printf("Couldn't open input file: %s\n", argv[1]);
    exit(1);
  }

  printf("Loading numbers from input file...\n");
  struct Numlist nums = getNumbersFromFile(fh);
  printf("Done loading %lu numbers.\n", nums.size);

  // sort the numbers
  struct Numlist sorted = radix(nums);

  // output the numbers in sorted order
  int i;
  for (i = 0; i < nums.size; i++) {
    printf("%i\n", nums.arr[i]);
  }
}