Counting Sort
Learn Counting Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Counting Sort - O(n + k), NOT Comparison-Based When elements are integers within a KNOWN, SMALL range [0, k] , counting sort beats every comparison-based sort's O(n log n) floor by never comparing elements at all - it counts occurrences of each value directly. Count how many times each value appears. Convert counts to a prefix sum - this gives each value's correct FINAL position. Place each element directly at its computed position.