algorithm - 如何获得基于 O(n log k) 时间比较的算法来对 k-multiset 进行排序？

Question

如果我有一个数组 {1,1,1,1,2,2,3,4,4,4,5,5} 这是一个排序的 5-multiset，大小为 n= 12，k = 5 (不同的键)。什么是基于 O(n log k) 时间比较的算法来为类似的未排序数组排序 k-multiset？我想到的方法是 3 向分区快速排序。

Answer 1

只需将元素插入平衡二叉搜索树即可产生所需的复杂性。树的每个节点都可以存储到目前为止输入中的值和这些值的计数，就像在计数排序中一样。树的大小最多为 k，插入次数为 n，因此总时间为 O(n log k)。二叉搜索树是基于比较的，因此满足要求。

如果以某种方式完全禁止使用计数，我们可以在树的每个节点中存储相等值的链表，即使只是为了 mock 这种要求。