Hire The World’s
Top Talent On Demand
Top Talent On Demand
AI EngineersAndroid DevelopersAngularJS DevelopersBigCommerce DevelopersC# DevelopersC++ DevelopersData Visualization DevelopersDrupal DevelopersFront-end DevelopersHTML5 DevelopersiOS DevelopersJava DevelopersKubernetes DevelopersMagento DevelopersMobile App DevelopersNode.js DevelopersOdoo DevelopersPHP DevelopersPython DevelopersQA EngineersReact.js DevelopersRemote DevelopersRuby on Rails DevelopersSalesforce ConsultantsSalesforce DevelopersShopify DevelopersSoftware DevelopersSquarespace DevelopersSvelte DevelopersTechnical WritersWeb DevelopersWebRTC DevelopersWooCommerce DevelopersWordPress DevelopersWPF Developers
Toptal connects the top 3% of freelance developers all over the world.
Few Unique Keys
Animation, code, analysis, and discussion of 8 sorting algorithms on few unique keys.
DISCUSSION
Sorting an array that consists of a small number of unique keys is common in practice. One would like an algorithm that adapts to O(n) time when the number of unique keys is O(1). In this example, there are 4 unique keys.
The traditional 2-way partitioning quicksort exhibits its worse-case O(n2) behavior here. For this reason, any quicksort implementation should use 3-way partitioning, where the array is partitioned into values less than, equal, and greater than the pivot. Because the pivot values need not be sorted recursively, 3-way quick sort adapts to O(n) time in this case.
Shell sort also adapts to few unique keys, though I do not know its time complexity in this case.
KEY
- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.
- Dark gray values denote the current interval (shell, merge, quick).
- A pair of red triangles marks the left and right pointers (quick).