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