Pseudo-Sorted array is an array that for every 0=<k<n the k smallest cell will be in the first 2k cells. For example the smallest cell will be in indexes 0-1 The second will be in indexes 0-3 The fifth will be in indexes 0-9 Etc. Is it possible to sort this array in O(n) time?

Thank you fellow people


2 Answers 2


It does not exist. An argument goes as follows. Suppose an algorithm exists that sorts your list in $O(n)$ time, then the same algorithm can be used to sort any list in $O(n)$ time as follows.

Given an arbitrary list $L$ of size $n$, find the smallest element in $O(n)$ time. Call this element $s$. Construct a new list $L'$ of size $2n$ whose elements are as follows. The first $n$ elements are $s-n, s-n+1, s-n+2, \ldots, s-1$ and the last $n$ elements are exactly the elements in the list $L$. This is again an operation that can be done in $O(n)$ time and $O(n)$ space.

Clearly $L'$ satisfies the condition that you had stated. Now, use your algorithm to sort the list $L'$ in $O(n)$ time and return the last $n$ elements of $L'$, which is the sorted version of the list $L$. Moreover, this is obtained in $O(n)$ time.

Since $O(n)$ time algorithm to sort an arbitrary list does not exist, the algorithm you seek does not exist as well.

Edit: I am precluding algorithms that are not comparison sorts. If you allow non-comparison sorts (like Radix sorts), then well, any list can be sorted in $O(nk)$ time where $k$ is the number of digits in any number.

  • $\begingroup$ If you are only considering comparison sorts, your "unlikely" can be turned into an impossible. The nlog(n) bound on sorting is known to b etight. $\endgroup$ Commented May 30 at 13:30
  • $\begingroup$ I agree. I have edited my answer now. $\endgroup$
    – Lisa E.
    Commented May 30 at 13:35

no. the easiest proof is a counting argument of how many such lists of size n there are. there's over (n/2)! (since the last half of the elements can be in any order) such lists which implies a time of n log(n)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.