Is it possible to make a sorting algorithm
That its running time at worst case is quadratic => n^2
But in most cases
(That is, on more than half of the n-size inputs)
the run time will be linear => n ??
I was thinking about Radix Sort and just make the worst case, worse
But I do not know if it is possible.
yes, the Bucket Sort
https://www.geeksforgeeks.org/bucket-sort-2/?ref=lbp
you can reed abut the algorithm in the link
In the worst case, we could have a bucket which contains all n values of the array. Since insertion sort has worst case running time O(n^2), so does Bucket sort. We can avoid this by using merge sort to sort each bucket instead, which has worst case running time O(n lg n).
Yes, it is possible.
Bucket sort analysis does reveal such behaviour (with reasonable number of buckets).
