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.
Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.