Frequency Count Sort: A Near-Linear Time Distribution Sort for Low-Entropy Datasets with Frequent Duplicates | IJCT Volume 13 – Issue 3 | IJCT-V13I3P122

This paper introduces Frequency Count Sort (FC-Sort), a distribution-based sorting algorithm designed explicitly for low-entropy datasets in which the number of unique keys u is substantially smaller than the total number of observations n. By reducing the sorting problem to the unique keys in the input list, that is, a frequency map of u unique keys, a sort of those keys alone, and then a linear reconstruction, FC-Sort achieves near-linear time complexity O(n + u²) that degrades gracefully as u grows and converges to O(n) within the defined problem domain of u ≤ 100. Empirical benchmarks across a broad configuration space (n ∈ {100,000 to 2,500,000}, u ∈ {5 to 100}) demonstrate and confirm that FC-Sort ranks first or remains statistically equivalent to the best-performing competitor (Counting Sort) in every optimized configuration tested within this domain. It has been established in the algorithms literature that 3-way Quicksort represents the optimal comparison-based approach for sorting all-identical key datasets, owing to its single equal-zone partition pass making it achieve linear O(n) time [1], [7]. This optimality is bounded by the requirement to examine every element/key. This paper demonstrates that FC-Sort, deploying a post-frequency-count early-exit heuristic, termed Homogeneity Test Heuristic (HTH), breaks that bound. In this specific all-equal keys domain, it achieves a strictly lower constant-factor cost by eliminating the sort and reconstruction phases entirely upon detection of u = 1. This reduces the total sorting task to a single O(n) frequency count pass — the theoretical minimum, since any algorithm must examine every element at least once. FC-Sort does not merely match the optimal comparison-based baseline of 3-Way Quicksort in this single key domain, it dominates it, achieving work that is asymptotically less and, for large n. The algorithm is intentionally simple: three stages, implementable from pseudocode in under 20 lines and portable across any language supporting hash-based associative structures. This simplicity is a feature and it lowers the barrier to adoption, auditing, reproducibility and verification. Two directions for future work are identified. First, considering that the algorithm demonstrates efficiency with some specialized dataset with equal keys, a fusion with another algorithm with O(nlogn) complexity in a hybrid design could potentially result in a very competitive O(nlogn) algorithm. Second, the algorithm design practically condenses the input list to the much smaller sub-list of unique keys, and given that the frequency count of all unique elements are known before the left to right serial expansion, a significant time incurred in serial writing to target list could be reduced under parallelism. This would mean that the writing to the target list of each or some unique elements could be assigned to separate processors in the machine such that writing operation occurs simultaneously saving time and thus improving runtime.