Difference between Comparison (QuickSort) and Non-Comparison (Counting Sort) based Sorting Algorithms? Example

For many of you, this might be a surprise that how you can sort or arrange items without comparing them with each other, but it's possible. There are some sorting algorithms that perform sorting without comparing the elements rather than making certain assumptions about the data they are going to sort. The process is known as non-comparison sorting and algorithms are known as the non-comparison-based sorting algorithms. Non-comparison sorting algorithms include Counting sort which sorts using key-value, Radix sort, which examines individual bits of keys, and Bucket Sort which examines bits of keys. These are also known as Liner sorting algorithms because they sort in O(n) time. They make certain assumptions about data hence they don't need to go through a comparison decision tree.

So, based upon how they work, you can broadly classify the sorting algorithms into two categories, comparison-based like QuickSort or MergeSort, and non-comparison based e.g. Counting sort or Radix Sort. As the name suggests, the fundamental difference between a comparison-based and a non-comparison-based sorting algorithm is the comparison decision.

In the first type, a comparator is required to compare numbers or items. Basically, this comparator defines the ordering like in the numerical order, lexicographical order, also known as dictionary order to arrange elements. 

On the other hand, non-comparison-based sorting algorithms don't use comparison but rely on integer arithmetic on keys. Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course to fill the gaps in your understanding.

Why Non-Comparison based Algorithms?

Some of you might be thinking why do we need non-comparison-based algorithms at all, isn't comparison-based sorting algorithms is enough? Well, if you look at the performance of the comparison-based sorting algorithm, you will realize that Bubble sort, Selection Sort, and Insertion sort takes around O(n^2) time to sort n items.

While, heap sort, quick sort, and merge sort takes O(NlogN) time in the best case and around O(n^2) in the worst case. 

Can we do better than O(NlogN) using the sorting algorithm? can we sort items in O(n) time using these sorting algorithms? Well, the answer is No.

It can be proven that any comparison-based sorting algorithm will take at least O(NlogN) operations to sort n elements, hence you need a non-comparison-based sorting algorithm that allows you to sort elements in linear time.

The linear sorting algorithms are also one of the popular data structure and algorithm questions in recent times, so you better know about it.

Comparison based Sorting vs NonComparison based Sorting

Due to the working difference between these two types of algorithms, generally, the non-comparison-based sorting algorithms like Radix Sort, Counting Sort, and Bucket Sort are faster than QuickSort, Merge Sort, and Heap Sort. Let's see a couple of more differences between these sorting algorithms to understand better.

The latter type is also known as Integer sort because it relies on integer arithmetic for sorting rather than comparison.


1. Speed 

One of the most critical differences between these two sorting algorithms is speed. Non-comparison sorting is usually faster than sorting because of not doing the comparison. The limit of speed for a comparison-based sorting algorithm is O(NlogN) while for non-comparison-based algorithms it's O(n) i.e. linear time.


2. Comparator 

Comparison based sorting algorithm like QuickSort, MergeSort. or Heap Sort requires a Comparator to sort elements e.g. while sorting an array of String, but non-comparison based sorting algorithms doesn't require any comparator.


3. Usage 

A non-Comparison-based sorting algorithm can use to sort any object provided it provides Comparator to define order, but a non-comparison-based sorting algorithm can not be used to sort anything other than integers, that's why they are also known as integer sorting. You can also see the Introduction of Algorithms to learn more about the O(n) sorting algorithms.

4. Examples

The QuickSort, MergeSort, Heap Sort, Selection Sort, Bubble Sort, and Insertion Sort, while some popular example of non-comparison based sorting is Radix Sort, Counting Sort, Bucket Sort, etc


5. Memory Complexity 

The best case for memory complexity with the comparison-based sorting is O(1) because it's possible to sort an array of numbers in place i.e. without using any additional memory. You can see the code for the in-place Quicksort algorithm here. On the other hand, memory complexity for the non-comparison-based sorting algorithm is always O(n).


6. CPU complexity 

The lower bound of CPU complexity or how much time it takes for the algorithm to sort N numbers in the worst case is O(NlogN), but in the case of non-comparison based sorting the CPU complexity lower bound is O(n) i.e. the worst case is even worse with non-comparison based sorting algorithms.

Here is a nice animation of some of the popular comparison-based sorting algorithms:

That's all about the difference between comparison and non-comparison-based sorting algorithms. Most of the common sorting algorithms fall into the category of comparison-based sorting algorithms like quicksort, mergesort, etc and those are the more likely you will use in the real world, but specialized non-comparison algorithms like counting sort and bucket sort can be very useful if the set of input meets the pre-conditions required. You can further read, Introduction to Algorithms by Thomas H. Cormen to learn more about non-comparison-based sorting algorithms e.g. bucket sort.


Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• 133 core Java interview questions of last 5 years (see here)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• Top 5 books on Programming/Coding Interviews (list)
• My Favorite Coding interview courses for Beginners (courses)
• 10 Free Data Structure and Algorithms courses (free courses)
• 100+ Data Structure and Algorithms Questions for Interviews (questions)

Thanks for reading this article so far. If you like this article then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you.