in this problem we are not sorting anything so how is the array sorted without making any kind of sort
Bucket sort problem
we make insertions into corresponding bucket and then travel across buckets in increasing/decreasing order ! this makes array sorted!
example: we have student along with their marks:
Ravi-50
Aryan-70
Mohit-87
we know that marks will be from 0 to 100, so we take 101 buckets!
we put students in bucket number equal to their marks
so Ravi goes to bucket 50, Mohit goes to bucket 87 and so on…
Now we travel from 100 to 0 and print/save students whenever there are some students in bucket!
From 100 to 88 all buckets are empty, so we move on
but bucket 87 has Mohit, so we print Mohit and move on.
This way array is sorted!