Radix Sort Tutorial

Hamburg (Germany), the 29th April 1997. Written by Nils Pipenbrinck aka Submissive/Cubic & $eeN

Introduction

This is a short tutorial on Radix-sort. If you already know what radix-sort is, how it works and you don't use quicksort anymore you can skip this tutorial. The tutorial is intended for programmers who have to write a fast sorting algorithm for small and medium sized lists. So if you want to sort a database you should search the web for another tutorial. If you however write a 3d-engine or such stuff you should read on because radix-sort is very good for this purpose.

The Basics

How do you sort a list if numbers? Basically you have an algorithm which compares numbers and tries to get the list more and more sorted. The Radix-sort is a little bit different. It doesn't compare anything, it sorts with several passes the numbers. Lets first start with a list of bytes. A very simple radix-sort for bytes would work like this:

a pseudo-code would sort the list this way:

for i=0 to source_n do
   dest[source[i]].append(source[i])

this means you append all items with value #1 to list 1, all items with value #2 to list 2 and so on. As you can see this algorithm runs very fast (it only copies the bytes in a very tight loop). The backdraw is, that you need a lot of memory to sort the list because you don't know how many items of each type you have.

Saving Memory

Do you really need to know how many items of each type you have? No, you can count them and optimize your memory-requirements. We'll need another loop to count the distribution of the source-values:

int distribution[256]

// fill the list with zeros.

for i=0 to 255 do
   distribution[i] = 0;

// build a distribution history:

for i=0 to source_n do
   distribution[source[i]] = distribution[source[i]] + 1;

// Now we build a index-list for each possible element:

int index[256];
index[0] = 0;

for i=1 to 255 do
   index[i] = index[i-1] + distribution[i-1];

adapting the old and simple radix-sort to take use of the new information will result in this code:

dest: array of bytes with space for source_n bytes.

for i = 0 to source_n do
   dest[index[source[i]]] = source[i];
   index[source[i]] = index[source[i]] + 1;

After this dest is the sorted source-array. As you can see we only need the same amount of memory as the sourcelist. This is quite a saving, and if your lists don't contain millions of values we can live with the memory-requirement.

Extending the Byte Sort

Who want's to sort bytes? You? I norally sort ascii-texts, floats or longints. Because I only want to explain how the extenstion works I'll go on with longints. If you want increase the size of the elements to sort you can do this in several ways. Either you increase the size of index and distribution or you sort in several passes. Increasing the size of the index only works for short values (sorting smallints would require at least 65536*2 bytes for index and distribution list which finally needs 256 kb of memory.. I think this is to much (only think about how long it takes to clear the memory and build the index-list.. In this time quicksort may have sorted your list already)). Now we need a clever way to sort more bits with the same memory-amount. We can do this with several passes. Let's do it in decimal.

unsorted list:
523
153
088
554
235

sorting for Radix 0 (least significant digit)
523
153
554
235
088
  ^
sorting for Radix 1 (2nd. significant digit)
523
235
153
554
088
 ^
sorting for Radix 2 (most. significant digit)
088
153
235
523
554
^

As you can se we preserve the old sorting order and advance by one digit until we've sorted all digits. This illustration did this in decimal. The native digit-format for computers are bits, bytes, words and dwords.

C(++) Example Code

I know.. real programmers code in assembler. (Hey! I thought you want to understand radix-sort, not assembly). The program compiles well under watcom c++. However, it should at least work on all 32-bit c compilers and on some 16 bit compilers.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>

#ifdef _WINDOWS
typedef unsigned long uint32_t;
typedef unsigned char uint8_t;
#else
#include <stdint.h>
#endif

static void radix(int byte, const unsigned N, const uint32_t *source, uint32_t *dest)
{
  unsigned count[256];
  unsigned index[256];
  memset(count, 0, sizeof (count));

  for(unsigned i=0; i<N; ++i)
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for(unsigned i=1; i<256; ++i)
    index[i] = index[i-1] + count[i-1];

  for(unsigned i=0; i<N; ++i)
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

void radixsort(uint32_t *source, const unsigned N)
{
  uint32_t *temp = new uint32_t[N];
  radix(0, N, source, temp);
  radix(1, N, temp, source);
  radix(2, N, source, temp);
  radix(3, N, temp, source);
  delete [] temp;
}

static void make_random(uint32_t *data, const unsigned N)
{
  for (unsigned i=0; i<N; ++i)
    data[i] = rand() | (rand()<<16);
}

static void check_order(const uint32_t *data, unsigned N)
{
  for(--N ; N > 0; --N, ++data)
    assert(data[0] <= data[1]);
}

int main()
{
  uint32_t data[100];
  make_random(data, 100);
  radixsort (data, 100);
  check_order(data, 100);
  return 0;
}

Reactions and Comments

I received some reactions from folks, who read this tutorial. There are some interesting sidenotes and implementation details which might be interesting for you.

Final Words

I hope you learned something. I have to thank Climax from Amable for makeing me interested in this algorithm. (well, some weeks before Assembly 1996 I still thought Quicksort would be the best algorithm to sort. Well, for ASCII-strings it still is, but for an engine... Hm.. Radix sort really rocks.) If you want to contact me you might write me a mail. Some of you might also notice, that this tutorial has been released at to the hornet archive in late 1996. However, I think this page is a better place for it.

© by submissive