Presenting An O(n) Sort Algorithm: ijk_sort

I’m pleased to announce that I’ve just developed a sorting algorithm in C++ whose worst case performance is O(n). I have named this algorithm ijk_sort (“ijk” is pronounced “ike” as in “Dijkstra“).

You can download the source of ijk_sort.cpp, reprinted below:


#include <limits .h>
using namespace std;
 
// via http://graphics.stanford.edu/~seander/bithacks.html
static const unsigned char ijk_cache[256] =
{
# define B2(n) n, n+1, n+1, n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
 
 
// sort an array "arr" of type "T" with "n" elements
// assumes CHAR_BIT == 8
template <class T> void ijk_sort(T* arr, unsigned long n)
{
unsigned char* a = (unsigned char*)arr;
unsigned long nn = sizeof(T) * n;
unsigned long zero = nn * CHAR_BIT;
 
for (unsigned long i = 0; i < nn; ++i)
zero -= ijk_cache[a[i]];
 
unsigned char h = (unsigned char) -1;
unsigned char m = h >> (zero % CHAR_BIT);
unsigned long l = zero / CHAR_BIT;
 
for (unsigned long i = 0; i < nn; ++i) a[i] = i < l ? 0 : i > l ? h : m; }  

Here's a test program for you:

#include "ijk_sort.cpp"
#include <stdio.h>
using namespace std;
 
int main(void)
{
unsigned char arr[3] = {0xFF, 0x00, 0x07};
 
printf("\nBefore ijk_sort: ");
for (int i=0; i<3; ++i)
printf("%02X ", arr[i]);
 
ijk_sort<unsigned char>(arr, 3);
 
printf("\nAfter ijk_sort: ");
for (int i=0; i<3; ++i)
printf("%02X ", arr[i]);
 
printf("\n");
return 0;
}

“The last thing you learn in any language are the jokes.”
— Pilar de la Torre

“I put the zeros over here and the ones over there.”
— Me