# Tag Info

1 vote

### Algorithm to sort array into K increasing subsets?

First, consider the case when $k$ is a perfect power of $2$. You find the median of the input array in $O(n)$ time using the Selection algorithm. Now take the median as the pivot to partition the ...
• 1,177

### Is there a lower bound on space complexity of non-in-place sorting?

You might be interested in external sorting, which can be viewed as loosely related to the study of sorting algorithms where the space complexity is much less than $O(n)$. In particular, we assume ...
• 161k
Accepted

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

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 ...
• 369
1 vote

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

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 ...
• 129

Top 50 recent answers are included