最高有效位基数排序比最低有效位基数排序效率如何？

Question

我只是在阅读以下问题： 基数排序最高有效还是最低有效，哪个更快？

接受答案的作者暗示，MSD基数排序确实更快。我不明白为什么。

我已经实现了LSD和MSD（通过执行移位操作来实现二进制），LSD是迭代的，只需要一个存储桶数组，而MSD是递归的，并且每个递归调用都需要一个单独的存储桶数组。

如果您创建一个由1000万个整数组成的随机数组，那么我将看不到MSD会比LSD快多少，因为每次您重新输入函数时都会分配额外的存储桶数组，并且您还必须面对递归调用的开销他们自己。

我可以看到MSD和LSD的组合如何带来整体提升（对前几位运行MSD，对其余位运行LSD以减少高速缓存未命中），但是单独的MSD有望比LSD更有效考虑到它的递归特性以及每个递归调用都需要一个新的存储桶数组这一事实，与LSD不同，LSD既是迭代的，又只需要一个存储桶数组来完成整个排序过程？

Answer 1

回答

MSD基数的迭代次数取决于输入大小，而LSD基数排序的迭代次数取决于密钥长度。这通常导致MSD基数排序比LSD基数排序所需的迭代次数少得多，因此速度更快。

内存分配不是问题，因为可以轻松就地实现MSD基数排序。

基本原理

我已经为LSD和MSD基数排序实现了一个实现，因此我可以看到它们具有哪些属性，这些属性使MSD基数排序比LSD基数排序更快。

我已经将它们的速度与std :: sort在一个100.000.000随机正63位整数数组上进行了比较（我使用了std :: sort的结果，我还将其用于验证排序后的数组），并得到以下结果：

• 纯LSD排序：10.5秒
• std :: sort：9.5秒
• 纯MSD排序：9.3秒
• MSD排序+ insert_sort：7.6秒

因此，它比std :: sort快一点，并且如果叶子用ins​​ert_sort排序，则要快很多。

为什么MSD基数排序比LSD基数排序快？

• 存在缓存局部性，尽管我怀疑这是否真的很重要，因为LSD基数排序也会扫描整个数组，而不是执行随机访问。
• 可以实现MSD基数排序，使其空间复杂度为O（dk），因此仅取决于基数d和项目k的长度。这可以在几乎是免费的堆栈上分配。因此，它基本上是一种就地排序算法。
• 底层可以修剪。即，当存储桶仅包含1个元素时，它已经被排序，因此不需要在该存储桶上递归。因此，MSD基数排序仅需要执行大约log（n）/ log（d）迭代。虽然LSD基数排序始终必须执行k次迭代。

我认为最后一点是MSD基数排序通常比LSD基数排序更快的原因。如果输入数据是均匀随机分布的，则预期运行时间为O（n log（n）/ log（d）），而LSD基数排序的运行时间为O（nk）。通常，n比k ^ d小很多。仅当n = o（k ^ d）时，LSD基数排序才会更快。但是，在这种情况下，也可以使用计数排序（k = 1的基数排序）。

实施

inline void insertion_sort(int64_t * array, int n) {
  for (int i=1; i<n; i++) {
    int64_t val = array[i];
    int j = i;
    while (j>0 && array[j-1] > val) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = val;
  }
}

void msd_sort(int64_t * array, int n, int64_t bit=60) {
  const int64_t mask = INT64_C(7);
  // Count bucket sizes
  int count[9]={};
  for (int i=0; i<n; i++) {
    count[((array[i]>>bit) & mask)+1]++;
  }
  // Create holes.
  int loc[8];
  int64_t unsorted[8];
  int live = 0;
  for (int i=0; i<8; i++) {
    loc[i] = count[i];
    count[i+1]+=count[i];
    unsorted[live] = array[loc[i]];
    if (loc[i] < count[i+1]) {
      live++;
    }
  }
  live--;
  // Perform sort
  for (int i=0; i<n; i++) {
    int64_t val = unsorted[live];
    int64_t d = (val>>bit) & mask;
    array[loc[d]] = val;
    loc[d]++;
    unsorted[live] = array[loc[d]];
    if (loc[d] == count[d+1]) {
      live--;
    }
  }
  if (bit>0) {
    for (int i=0; i<8; i++) {
      n = count[i+1] - count[i];
      if (n > 20) { // If replaced by n > 1, insertion_sort is not needed.
        msd_sort(array + count[i], n, bit-3);
      } else {
        insertion_sort(array + count[i], n);
      }
    }
  }
}

void lsd_sort(int64_t * array, int n) {
  const int64_t mask = INT64_C(7);
  std::vector<int64_t> buffer(n);
  for (int64_t bit=0; bit<63; bit+=3) {
    // Copy and count
    int count[9]={};
    for (int i=0; i<n; i++) {
      buffer[i] = array[i];
      count[((array[i]>>bit) & mask) + 1]++;
    }
    // Init writer positions
    for (int i=0; i<8; i++) {
      count[i+1]+=count[i];
    }
    // Perform sort
    for (int i=0; i<n; i++) {
      int64_t val = buffer[i];
      int64_t d = (val>>bit) & mask;
      array[count[d]] = val;
      count[d]++;
    }
  }
}