# Question: Show that there is no comparison sort whose

Show that there is no comparison sort whose running time is linear for at least half of the n! input of length n. What about a fraction of 1/n of the inputs of length n? What about a fraction 1/2n?

## Relevant Questions

Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a ¬ b] in O (1) time. Your algorithm should use Θ ...What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(n lg n)?We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for ...We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an in order tree walk. ...Given an element x in an n-node order-statistic tree and a natural number i, how can the ith successor of x in the linear order of the tree be determined in O(lg n) time?Post your question