梅子的Programming Pearls Problems Solutions(Column 1)，然后我在filipegoncalves的基础上改成了多线程的版本。

10000000个数排序在200ms内。

//

//  main.cpp

//  bitmap_sort

//

//  Created by Ryza 15/11/9.

//  Copyright © 2015年 [data deleted]. All rights reserved.

//

#include <stdio.h>

#include <limits.h>

#include <fcntl.h>

#include <sys/mman.h>

#include <unistd.h>

#include <pthread.h>

#define MAXINT 10000000

#define CHAR_BIT_LOG 3 /* assumes that CHAR_BIT == 8, so log_2(8) = 3 */

#define MASK (~(~0 << CHAR_BIT_LOG))

#define setbit(a, x) ((a)[(x) >> CHAR_BIT_LOG] |= 1 << ((x) & MASK))

#define isset(a, x) ((a)[(x) >> CHAR_BIT_LOG] & (1 << ((x) & MASK)))

char array[MAXINT + 1];

char * mbuf = NULL;

off_t len;

#define number_of_threads 8

pthread_t sort_tids[number_of_threads];

off_t parts[number_of_threads + 1] = { 0 };

void printnumbers();

void analyse(char *, off_t, off_t);

void * thread(void * arg) {

    analyse(mbuf, parts[(long)(off_t *)arg], parts[(long)(off_t *)arg + 1]);

    return nullptr;

}

int main(int argc, char *argv[]) {

    if (argc != 2) {

        fprintf(stderr, "[%s] Usage: %s input-file\n", argv[0], argv[0]);

        return 1;

    }

    

    int fd = open(argv[1], O_RDONLY);

    if (fd == 0) {

        fprintf(stderr, "[%s] Could not open file %s\n", argv[0], argv[1]);

        return 1;

    }

    len = lseek(fd, 0, SEEK_END);

    mbuf = (char *)mmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);

    

    parts[number_of_threads] = len;

    for (int i = 1; i < number_of_threads; i++) {

        parts[i] = len / number_of_threads * i;

        while (mbuf[parts[i]] != ' ') {

            parts[i]++;

        }

    }

    

    for (int i = 0; i < number_of_threads; i++) {

        pthread_create(&(sort_tids[i]), NULL, thread, reinterpret_cast<void *>(i));

        pthread_join(sort_tids[i], NULL);

    }

    

    printnumbers();

    return 0;

}

void analyse(char *buf, off_t from, off_t to) {

    long long number = 0;

    for (char *p=(char*)((long)(char*)buf + from);*p && p - buf < to; p++) {

        if (*p == ' ') {

            setbit(array, number);

            number = 0;

        } else {

            number = number * 10 + *p - '0';

        }

    }

}

void printnumbers() {

    int i;

    for (i = 0; i <= MAXINT; i++)

        if (isset(array, i))

            printf("%d ", i);

}