As similar to Counting Sort, Bucket sort also imposes restrictions on the input to improve the performance. In other words, Bucket sort works well if the input is drawn from fixed set. Bucket sort is the generalization of counting sort. For example, suppose that all the input elements from [0, 1, ……, K-1] , i.e. the set of integers in the interval [0, K-1]. That means, K is the number of elements in the input. Bucket sort uses K counters. The ith counter keeps track of the number of the ith element. Bucket sort with two buckets is effectively a version of Quick sort with two buckets.

Here is a partial code for the bucket sort algorithm

#define BUCKETS 10 void bucketSort(int arr[], int size) { int i,j,k; int buckets[BUCKETS]; for(j = 0;j < BUCKETS;j++) buckets[j] = 0; for(i = 0;i < size;i++) ++buckets[arr[i]]; for(i = 0, j = 0;j < BUCKETS; j++) for(k = buckets[j];k > 0; --k) arr[i++] = j; }

*Time Complexity:-* O(n)

*Space Complexity:-* O(n)