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
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.
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)
