# Is it possible to sort this type of array in O(n) time?

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.

• 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. Commented May 30 at 13:30
• I agree. I have edited my answer now. 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)