Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why?
How would one justify the answer to the above question logically? Logically as in without implementing the algorithms and finding the average time consumed for few sample data sets.
All elements being the same is equivalent to data being sorted. The class of algorithms you are looking for is adaptive sort, which benefits from presortedness of the input data - this is the justification - since data is already sorted we have to find algorithm that uses this fact. The classic example is the insertion sort, but also Timsort (a variant of natural merge sort) and other exist. All adaptive algorithms should show the best case performance as $\mathcal{O}(N)$, which in case of insertion sort is exactly $N - 1$ comparisons, where $N$ is the length of input data.
There is no need to implement or run those algorithms, it is suficcient to show that part responsible for swapping elements is never executed, show that appropriate conditions are always true (or false depending on code) so analysis is easier.
From the possible algorithms you have provided the best cases are: Bubble sort - $\mathcal{O}(N)$, Selection Sort - $\mathcal{O}(N^2)$ and Insertion Sort - $\mathcal{O}(N)$.
