  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.
