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

if I have an array {1,1,1,1,2,2,3,4,4,4,5,5} this is a sorted 5-multiset of size n= 12, and k = 5 (distinct keys). What is a O(n log k)-time comparison-based algorithm to sort k-multiset for a similar unsorted array? The approach I had in mind is 3-way partition quick sort.if I have an array {1,1,1,1,2,2,3,4,4,4,5,5} th