algorithm - 平滑排序算法在哪里使用？

Question

在我的大学学习算法时，我遇到了一种称为平滑排序的算法。它是一种很棒的算法，因为它是一种自适应算法，时间复杂度可以从线性复杂度到线性复杂度不等，而且它也是一种就地算法。但是，该算法的资源非常稀缺，而且很难理解。但是，我发布这个问题的原因是为了了解用例以及何时应该使用它以及何时不应该使用它？
这就是我想知道的全部内容，非常感谢您回答或审查这个问题。

Answer 1

musl libc 使用 Smoothsort 实现 qsort() . This Stack Overflow answer from the library author描述推理:最坏情况 O(n log n)(与快速排序不同)、就地(与合并排序不同)和自适应(与堆排序不同)。我认为对于某些组合，Smoothsort 并没有得到太多使用

Smoothsort 是不稳定的，在实践中稳定性往往比 in-place 更可取，因为这意味着存在相同键时的排序顺序是完全确定的。 musl 具有 C 标准允许的不稳定的自由度，设计目标之一是除非明确请求否则不分配内存(这就是为什么 musl strstr() 不使用 KMP，例如)。
请注意，存在就地、稳定、O(n log n) 时间排序算法，但常数因子太大而不实用。

自适应性更好，而且平滑排序比堆排序更复杂。

Smoothsort 并不广为人知，因为它在几乎所有本科算法类(class)(甚至研究生类(class)——例如，我在学校没有看到它)中都被遗漏了。