Question

Suggest how any sorting algorithm can be augmented in a way to make the best-case count of its key comparisons equal to just n−1( n is a list’s size, of course). Do you think it would be a worthwhile addition to any sorting algorithm?

Answer 1

Before applying a sorting algorithm,There is a need to compare the adjacent elements of its input (if ai ≤ ai+1 for every i = 0, .., n − 2, stop) before a sorting algorithm can be applied.

It slows down the algorithm, so for this reason it won't be a worthwhile addition.

This test is incorporated in the body of the algorithm by some sorting algorithms.