Linear Time Sorting

Why comparison based algorithms cannot sort in less than O(nlogn). And why counting sort, radix sort and bucket sort can do better.

Hi Friends,

Welcome to the 65th issue of the Polymathic Engineer newsletter. This week, we discuss algorithms capable of sorting array elements in linear time.

The outline will be as follows:

• Performance limits of comparison-based algorithms

• Counting Sort

• Radix Sort

• Bucket Sort

• Interesting posts