There is an implementation of this already but I'm not really satisfied with the results. I'd like to get a good feeling on whether this is really a linear growth algorithm. And, if so, what range of N is it suitable for?
The idea is that we build the long array as usual but then use bucket sort on the long values. Provided that we use a cleanup sort like insertion sort of Timsort, the overall process should be linear.
There is an implementation of this already but I'm not really satisfied with the results. I'd like to get a good feeling on whether this is really a linear growth algorithm. And, if so, what range of N is it suitable for?
The idea is that we build the long array as usual but then use bucket sort on the long values. Provided that we use a cleanup sort like insertion sort of Timsort, the overall process should be linear.