sleepsort: tricky sort using fork

hacker_compsleepsort is a parallel and arguably O(n) sorting algorithm that makes clever usage of the fork() function. fork() is an API to spawn a new child process. The program appeared in 4chan forum in Jan 2011. I modified it slightly to ignore negative inputs [sleep() takes unsigned in seconds]. Here’s the program:

#include <unistd.h>
#include <stdio.h>

int main(int c, char **v)
{
        while (--c > 1 && !fork());

        int val = atoi(v[c]);
        if (val < 0)
                return 0;
        sleep(val);
        printf("%d\n", val);
        return 0;
}

The output of the program in my system:

$ ./sleepsort 4 1 3 2 7 -5 0 9 5 8
0
1
2
3
4
5
7
8
$ 9

 The demonstration is strictly a clever and academic one and the results might vary on large number of inputs. Also, note that though the algorithm can be claimed to be O(n), it is non-deterministic and depends on the order the child processes run. For nanosleep() values in milliseconds or microseconds the result might not be sorted. A sleep() in seconds yields good results and is linear but it is much higher than the time needed to complete an atomic CPU instruction. Imagine a sequence to sort with 86400 as an element!!! 😉

Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s