Stop Comparing Data: Master Counting Sort!

Added: 2026-05-28

[00:00:00]What if I told you that you could sort an array faster than the mathematical limits of O of N log N? Welcome to counting sort, which is the cheat code that achieves linear time complexity by stopping normal comparisons you do with an arrays when it comes to sorting. The idea behind it is to compare instead of counting. So, instead of comparing two numbers, we're going to create a frequency array. We iterate through the input array once [music] and count how many times each of the values will appear. If we see three twos for instance, we're going to mark that down.

[00:00:29]We aren't moving elements, we're collecting data instead. And after that, we do a reassembly, which means that we're going to use those counts to determine the exact position of each element within the output [music] array.

[00:00:39]By calculating these cumulative totals, we know exactly where the fours will start and the sevens will end. One final pass throughout the data within our array is going to result in it being perfectly sorted within O of N plus K time. The trade-off of counting sort is that you need to know the range of the data that you're working with in advance. If your numbers are spread too far apart, the overhead of the frequency array that you're making can become a huge bottleneck within your sorting algorithm. It's a very specialized tool that can be used to deal with very dense arrays. I'm making more videos like these to go over sorting algorithms and other foundational CS concepts. If you like this video, be sure to like, comment, share, and subscribe, and mention your thoughts down below. I'll see you in the next one.