0
$\begingroup$

I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

It performs as follow:

$ gcc bench.c -lm
$ ./a.out 
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

I know that Quick Sort will perform in O(n log n) while Radix Sort will be in O(d (n + r)) ~= O(6 * n). For n = 52428800, log(n) = 17. I am then expecting Radix Sort to be 3 times faster than Quick Sort...

This is not what I observe.

What am I missing?

$\endgroup$
  • $\begingroup$ Big O hides constant factors. Your calculations are completely unhelpful, since you don't know the constant factors involved. Moreover, the actual complexity is usually not (say) $Cn\log n$, but rather there are some low order terms, which are more prominent for small $n$, and make it hard to predict break-even points. $\endgroup$ – Yuval Filmus Apr 29 at 13:08
  • $\begingroup$ Is there any tweaks I can use to make the observations more accurate? $\endgroup$ – nowox Apr 29 at 13:10
  • $\begingroup$ The correct thing to do, whenever you can do it, is profiling. $\endgroup$ – Yuval Filmus Apr 29 at 13:12
3
$\begingroup$
  1. qsort is not Quicksort. qsort is whatever the implementor of the standard library decided.

  2. Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time.

  3. Radix sort of 50 million numbers with six digits is obviously nonsense. Six digits means you expect only 64 different values and therefore would use counting sort. With less than 26 digits it doesn't make sense.

  4. Your radix sort does an awful lot of copying, and worse, uncached copying.

  5. Your radix sort doesn't produce a correctly sorted result if digits is an odd number.

  6. Your qsort call doesn't produce a correctly sorted result if the array contains very large and very small numbers.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why are my copying awful? What do you mean by uncached copying? Usually radix sort is not a in place sorting algorithm I read. $\endgroup$ – nowox Apr 29 at 18:21
  • $\begingroup$ Typically copying = nanosecond, copying outside the processor cache which will be a few mb at most = 100 of nanoseconds. But try realistic values. 50 million zeroes is not realistic. $\endgroup$ – gnasher729 Apr 30 at 5:40
  • $\begingroup$ radix sort is usually performed on 1 byte in each pass. also, there is a trick that significantly speed ups radix sort - compare naive and good radix sorts here: github.com/Bulat-Ziganshin/MT-LZ/blob/master/RadixSort.cpp#L38 $\endgroup$ – Bulat Apr 30 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.