Replacement sort revisited: The “gold standard” unearthed!

We argue that the new model in our opinion can be a guiding factor in distinguishing this algorithm from other sorting algorithms of similar order of average complexity such as bubble sort and insertion sort. Note carefully that the dependence of the number of interchanges on the parameters is more prominent for discrete distributions rather than continuous ones and we suspect this to be because the probability of a tie is zero in a continuous case. However, presence of ties and their relative positions in the array is crucial for discrete cases. And this is precisely where the parameters of the input distribution come into play. Those algorithms where ties have a greater influence on some of the computations will have greater influence of parameters of the input distribution in it. Another strength of the paper is that it brings up the close connection between algorithmic complexity and computer experiments, a crucial issue which is overlooked in the textbooks on algorithms. This is a paper on modeling rather than speed.