Permutations in an k-sorted array

Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.

I have a question in my Algorithms assignment which asks to prove the lower bound to sort a $k$-sorted array as $\Omega(n\log{k})$. I was trying to approach this question by using the standard comparison sort proof ($\Omega(n!)$), where we have $n!$ total permutations of the sequence [$a_1,a_2,\cdots,a_n$]. My friend told me that there are $k^{(n-k)}k!$ permutations of a $k$-sorted array. I'm finding it difficult to prove the same. How should I go about finding the total permutations of a $k$-sorted array?

Try for $n=5$, $k=2$.

Total permutation is $3\times 3\times 3\times 2\times 1$, First element has 3 possibilities $\{1,2,3\}$; second has 4 possibilities $\{1,2,3,4\}$, but one position is already taken by the first,so effectively it has $(4-1)$ slots; third has 5 possibilities $\{1,2,3,4,5\}$, but first and second are there in one of these two, hence 3 possibilities; Fouth one has 4 slots $\{2,3,4,5\}$ and 3 of them are taken? (doubt: because 1st position can also be occupied) , hence 2 , and the last has one.

• (1) Every $k$-sorted array is also $k+i$-sorted, for $i>0$. So the problem gets easier with increasing $k$. Your lower bound on the other hand gets larger with increasing $k$. That seems off. (2) The formula from your friend claims that there is only a snigle 1-sorted permutation, which is wrong. Sep 24, 2014 at 7:25
• You never mentioned what kind of lower bound you're interested in. I'm assuming you want to sort a $k$-sorted array, in which case you will need at least $\log_2 N_k$ comparisons, where $N_k$ is the number of $k$-sorted arrays. If so, please make that clear. Sep 24, 2014 at 13:40
• @FrankW The smaller the $k$, the stronger the promise on the input array, so the easier the problem is (assuming the problem is indeed to sort the array). Sep 24, 2014 at 13:40
• I was assuming that the task is to go from unsorted to $k$-sorted. Now I see, this is indeed unspecified. Sep 24, 2014 at 13:47

Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\{1,\ldots,n\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total, $$k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\ \frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1)$$ We conclude that $\log N(n,k) = \Theta(n \log k)$.
• You might be disappointed, as there is no nice formula for $N(n,k)$. For example, for $k=1$ you get the Fibonacci numbers, and it only gets more complicated, though for every given $k$ you can write a reasonably simple formula. I added a reference giving this formula. Sep 24, 2014 at 15:13
• Perhaps it's better you worked it out yourself. Try to see how the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ connects to $1$-sorted permutations. You could even look at some examples, that is, lists of all $1$-sorted permutations for small $n$. The same general idea leads to the formula given in the link. Sep 24, 2014 at 16:35