Floating point cardinality sort

During this time, when studying the external sorting of massive floating-point numbers, I studied some algorithms of internal sorting, and never thought about cardinality sorting. I happened to see it these two days RadixSortRevisited This article, deeply touched, wants to try to reproduce the cardinality sorting algorithm of lower floating point numbers.

The traditional cardinality sorting principle is to segment integers by bits, and then compare them by each bit. This method has a lot of information on the Internet, so I won't repeat it one by one here.

According to IEEE754 standard, double type data will be divided into 1, 11 and 52 segments in storage. 1 represents the number symbol, 11 represents the order code, and 52 represents the mantissa. For specific standards, please refer to relevant materials.

The first step of the algorithm is to understand that the data of double type is forcibly transformed into unsigned long integer for cardinality sorting. Since the data of double type occupies 64 bits, we can consider dividing the 64 bits into four parts, for example, 16 bits in each part, that is, the size of the bucket is 65536. It can be compared with decimal radix sorting. The size of each bucket in decimal radix sorting is 10, and after floating-point numbers are divided in this way, the size of each partial bucket is 65536.

The second step of the algorithm is to understand how to sort the cardinality after forcibly converting these floating-point numbers. It can be found that the number sign bit of a positive number is always 0 and the number sign bit of a negative number is always 1. Therefore, the final sorted result: small positive number - large positive number - large negative number - small negative number.

The third step of the algorithm is to adjust the sorted order, that is, the sorted result is corrected to negative small - negative large - positive small - positive large. In this step, we need to count the number of negative or positive numbers before. It will be more convenient to count the number of negative numbers here.

After roughly describing the steps of the following algorithm, the code is as follows:

// How floating point numbers are stored in the computer: https://www.cnblogs.com/jillzhang/archive/2007/06/24/793901.html
// https://www.boatsky.com/blog/26
// http://www.codercorner.com/RadixSortRevisited.htm
// Try to divide 250 million into 8 and 4. The effect of dividing into 4 is the best, but both are better than the built-in sort in C + +
void in_sort(double *buffer, long long n, int sort_seq_num) {
  // There are 64 bits in total. If it is sorted by every two bytes (16 bits), it is sorted by analogy with the base of decimal system, so it is divided into 4 parts. At this time
  // sort_seq_num = 4
  // There is a bucket array every 16 bits. The size of the array is 65536. The bucket array is counted
  int bit_num = 64 / sort_seq_num;
  int *bucket = new int[1 << (bit_num)];
  // Temporary storage
  auto *temp = (double *)malloc((n + 100) * sizeof(double));
  long long negative_num = 0; //Record the number of negative numbers
  // Converts a number to an unsigned long integer and sorts it cardinally
  for (int i = 0; i < sort_seq_num; i++) {
    for (int j = 0; j < (1 << bit_num); ++j) {
      bucket[j] = 0;
    }
    for (long long j = 0; j < n; j++) {
      if (i == 0 && buffer[j] < 0) {
        negative_num++;
      }
      int idx;
      unsigned long long val;
      val = reinterpret_cast<unsigned long long &>(buffer[j]);
      idx = val >> i * bit_num & ((1 << bit_num) - 1); //Extract every 16 bits
      bucket[idx]++;
    }
    //Find the boundary index of the base bucket
    for (int j = 1; j < (1 << bit_num); j++) {
      bucket[j] = bucket[j - 1] + bucket[j];
    }
    //Scan from right to left to ensure the stability of sorting and record it in temp
    for (long long j = n - 1; j >= 0; j--) {
      int idx;
      unsigned long long val;
      val = reinterpret_cast<unsigned long long &>(buffer[j]);
      idx = val >> i * bit_num & ((1 << bit_num) - 1);
      temp[--bucket[idx]] = buffer[j];
    }
    for (long long j = 0; j < n; j++) {
      buffer[j] = temp[j];
    }
  }
  // Handle negative numbers
  for (long long i = 0; i < n; i++) {
    if (temp[i] < 0.0) {
      buffer[n - 1 - i] = temp[i];
    } else {
      buffer[negative_num + i] = temp[i];
    }
  }
  free(temp);
}

Where sort_seq_num represents how many parts a 64 bit long integer is divided into, that is, how many times the second step of the algorithm needs to be compared.