论文标题
使用Mergesort在线性时间中使用平等键进行排序列表
Sorting Lists with Equal Keys Using Mergesort in Linear Time
论文作者
论文摘要
本文介绍了一种新的优化方法，以提高Mergesort的运行时复杂性，当对具有$ O（n log_2 K）$的键相等的键进行排序时，其中$ k $是序列中不同键的数量。当$ k $恒定时，很明显，Mergesort能够通过将链接列表作为其基础数据结构来实现线性时间。 Mergesort链接的列表实现可以通过将新机制引入相等键的组元素来优化，从而允许合并算法实现线性时间。
This article introduces a new optimization method to improve mergesort's runtime complexity, when sorting sequences that have equal keys to $O(n log_2 k)$, where $k$ is the number of distinct keys in the sequence. When $k$ is constant, it is evident that mergesort is capable of achieving linear time by utilizing linked lists as its underlying data structure. Mergesort linked list implementations can be optimized by introducing a new mechanism to group elements with equal keys together, thus allowing merge algorithm to achieve linear time.
