Sorting Algorithms - Bucket Sort


Now as we have learnt the methods to efficiently sort an array with O(n*log(n)) time complexity, in many cases it still can be inefficient.

If a scenario arrives where time complexity should strictly be less, we can compromise space complexity to make sorting efficient in terms of time complexity.


Here we will make buckets of a certain size and put the elements falling in that range into those buckets.

For e.g. If a sequence contains numbers lying in range 1-100, we can make buckets of size 10 which means, initially there will be 10 buckets of size 10 which will be accommodating the elements of the sequence.

Elements in the range 1-10 will go to the 1st bucket, and those lying in the range 11-20 will go to the 2nd bucket and so on. While inserting elements in their respective buckets we will compare them with elements already present in that bucket and thus make sure elements are placed in ascending order in these buckets.

Now we will start extracting elements from the sequence of these buckets in ascending order. The elements will be placed in original sequence in ascending order.

Here is an animation that will be helpful in understanding this concept:

















Implementation of Bucket sort is on its way:


So that’s it for this article we will be coming up with our next article on further topics very soon till then keep learning, keep coding, keep reading and keep improving !!



Happy Coding 😊

By Programmers Army