Skip to main content

New answers tagged

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 ...
codeR's user avatar
  • 1,177
0 votes

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 ...
D.W.'s user avatar
  • 161k
3 votes
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 ...
Lisa E.'s user avatar
  • 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 ...
Oscar Smith's user avatar

Top 50 recent answers are included