# Finding most efficient sorting algorithm

Arr is an array that contains $$n$$ numbers.
Suggest the most efficient algorithm for each case and analyze the runtime.
Explain why the algorithm you chose is the best one.

1. Arr contains exactly $$\frac{n}{5}$$ distinct values.
2. Arr contains integers in the range $$[0, … , 𝑛^7 − 1]$$.
3. There are exactly (𝑛 − √𝑛) integers in Arr, which are between 1 to 100. The remaining √𝑛 elements are not integers.

I was trying to look at some of the sorting algorithms and try to figure one by one which one is the best, but I believe there’s a better way to do it. What would be the right approach?