<p>Option 0: <a href="https://citeseerx.ist.psu.edu/pdf/6bb4d720088c4e0b2b039e174d34d2e0fd27c466" rel="nofollow noreferrer">Permuting In Place</a> (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete <span class="math-container">$O(n \log n)$</span> time <span class="math-container">$O( \log^{2} n )$</span> space.</p>
<p>Option 1: Cheat by compressing your permutation to a succinct data structure, see <a href="https://www.imsc.res.in/%7Evraman/pub/icalp_03.pdf" rel="nofollow noreferrer">Succinct representation of permutations</a>.</p>
<p>Option 2:  Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat <a href="http://oeis.org/A186202" rel="nofollow noreferrer">http://oeis.org/A186202</a></p>
<p>Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. <span class="math-container">$O(n^2)$</span> time, <span class="math-container">$O(\#\text{cycles} * \log n)$</span> space.</p>
<p>Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. <span class="math-container">$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$</span> time, <span class="math-container">$O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$</span> space.</p>
<p>Option 5: From same paper by Munro as Option 0, For <span class="math-container">$i = 1 .. n$</span> rotate the cycle of <span class="math-container">$p(i)$</span> if <span class="math-container">$i$</span> is the largest index in that cycle. <span class="math-container">$O(n^2)$</span> time and <span class="math-container">$O(\log  n)$</span> space.</p>

CC BY-SA 3.0
2014-01-21T23:01:37.347Z
the compression methods may not save space in general: the worst case space to store a permutation is $n\log n$. 3, 4, and 5 seem in general as bad as either the solution OP already knows, or the solution by Fich, Munro, and Poblete. And that solution was already pointed out by @Jukka
Sasho Nikolov
CC BY-SA 3.0
2014-01-21T23:04:17.507Z
#5 uses less space than #0 by a log (n) factor.
Chad Brewbaker
CC BY-SA 4.0
2014-01-21T18:26:57.300Z
2023-01-09T15:13:06.193Z
2023-01-09T15:13:06.193Z
Chad Brewbaker
<p>If you use the cycle representation of the permutation, you need 1 additional array element to store the item currently being permuted and you can run through the cycles in at worse O(N) operations.</p>

CC BY-SA 3.0
2013-07-25T20:15:23.297Z
jkff already said he knows the cycle-following algorithm, so he clearly wants the permutation itself to be treated as (close to) a black box. As he points out in the question, converting from a (nearly) black box to cycle representation could take O(n^2) time.
Joshua Grochow
CC BY-SA 3.0
2014-01-21T17:51:42.290Z
Black box p(i) is fine. You just go around the cycle until you get back to i. The problem is one of Kolomogorov complexity to store the list of items that have been updated so you don't cycle them multiple times. Munro has bounds on that. http://www.itu.dk/people/ssrao/icalp03-a.pdf
Chad Brewbaker
CC BY-SA 3.0
2013-07-25T02:20:48.400Z
2013-07-25T02:20:48.400Z
Phil
<p>First off, I came up with the same algorithm as mentioned by Russell Easterly but I have an additional tweak.</p>
<p>This is the initial algorithm:</p>
<p><code>for each </code><strong><code>increasing</code></strong><code> index i from 1 to length of array</code></p>
<p><code>   move</code><strong><code>along the permutation cycle of the current element</code></strong><code>starting at</code><span class="math-container">$f(i)$</span><code> and</code></p>
<p><code>       stop at the first permutation entry</code><span class="math-container">$k = f(j)$</span><code>where</code><span class="math-container">$j \le i &lt; k$</span></p>
<p><code>       or else</code><span class="math-container">$k = NaN$</span></p>
<p><code>   swap array element at i with element at k</code><strong><code>if k is not NaN</code></strong></p>
<p>This alone has a worst-case which is only twice as fast as the algorithm in the OP. But the common average case is much faster. For infinitely large N – under consideration of the geometric distribution of randomly generated permutation functions with <span class="math-container">$p = P(f(j) &gt; i) = 0.5$</span> for all <span class="math-container">$j,i$</span>, we would get N times the expectancy value which is <span class="math-container">$\mathcal{O}(N)$</span> time complexity with <span class="math-container">$\mathcal{O}(1)$</span> space complexity but it might be worse for real data with finite arrays where the parameter of the geometric distribution is a random process. It is certainly a faster and easier algorithm to implement than the one in the original post.</p>
<p>Now we can optimize the worst case by introducing an opposite function which goes into opposite direction, with decreasing index from last to first and searching for a <span class="math-container">$f(j \ge i) &lt; i$</span> each time.</p>
<p>Count the number of permutation lookups of both functions without swapping. Then choose the function with less required lookups to do the job with swapping. You can count in parallel or interleaved (assume a fair share of time so that the slower function does not get most of the time) and interrupt the counting of the slower function when it exceeds the returned count of the faster one. This case, we avoid degenerate cases and probably get a solid average case complexity as worst case (I conjecture). If this is true it would only take 3 times the average complexity of the initial algorithm which is better than square complexity in time and is guaranteed to have constant space complexity since no copies are created and swaps are inplace.</p>
<h4>Option 2</h4>
<p>I found an inplace-algorithm with assumed (measured) worst case <span class="math-container">$\mathcal{O}(N·log2(N))$</span>. I thought about avoiding unnecessary visits of permutation entries and noticed that the relation between the index and its permutation entry and is already some kind of binary flag property. Python-Code:</p>
<pre><code>def compute_permutation(array, pi):
    for i in range(len(array)):
        if (j := pi[i]) &gt; i:
            array[i], array[j] = array[j], array[i]
    
    for i in range(len(array)-1,0, -1):
        if (j := pi[i]) &lt; i:
            while pi[j] &gt; j or j &gt; i:
                j = pi[j]
            array[i], array[j] = array[j], array[i]
</code></pre>
<p>The algorithm yet allows for some further optimizations like avoiding walking through the full cycle for the first permutation entry which points back. I wonder, if walking through the cycles a logarithmic number of times is actually necessary when there are only few array elements left at position &lt; i.</p>
<h4>Option 3</h4>
<p>For a special case with mutable permutation, if destroying the permutation is not minded, then you can do this (Python):</p>
<pre><code>def compute_permutation(array, pi):
    for i in range(len(array)):
        j = i
        while i != (k := pi[i]):
            array[j], array[k] = array[k], array[j]
            pi[i], pi[k] = pi[k], pi[i]
            j = k
</code></pre>
<p>Does not allocate additional memory besides local variables and has <span class="math-container">$\mathcal{O}(N)$</span> time complexity and <span class="math-container">$\mathcal{O}(1)$</span> space complexity. The trick is to exploit the permutation as buffer which turns it into a linear range of indices at the end. This is probably not worse than the compression options found in the answer of Chad Brewbaker which also destroys the original value of the permutation entries.</p>
<h4>Option 4</h4>
<p>If there is a way to extract the original index from a given array-element in <span class="math-container">$\mathcal{O}(1)$</span> steps and space via a function <code>index_of()</code> then you can do even better without modifying the permutation function but same complexity lower bounds. Just use the comparison of that element index against the permutation entry as a flag:</p>
<pre><code>def compute_permutation(array, pi):
    for i in range(len(array)):
        if array[i].index_of() != pi[i]:
            j = i
            while i != (k := pi[j]):
                array[j], array[k] = array[k], array[j]
                j = k
</code></pre>
<h4>Option 5</h4>
<p>If there is no way to extract the original index of a value in <span class="math-container">$\mathcal{O}(1)$</span> time then there is still a way that will always work in practice, even though some could consider it cheating. You can use signed indices and use the sign bit as a flag that is cleared at the end of the algorithm. Set the flag for permutation entries whose corresponding element was already swapped to the correct position. This is always feasible in practice, at least in Java which always reserves a sign bit for integer values even though it is useless for indices.</p>
<pre><code>void compute_permutation(Object[] array, int[] pi)
{
    for(int i=0; i&lt;array.length; i++)
    {
        if (pi[i] &gt;= 0)
        {
            for(int j=i, k; i != (k = pi[j]); j = k)
            {
                Object tmp = array[j];
                array[j] = array[k];
                array[k] = tmp;
                pi[j] = ~pi[j];
            }
        }
    }

    for(int i=0; i&lt;pi.length; i++) pi[i] = ~pi[i];
}
</code></pre>
<p>This allows for practical inplace solutions with <span class="math-container">$\mathcal{O}(N)$</span> overhead and no additional allocation. Only restriction: requires a writable permutation array.</p>
<p><em><strong>Big disadvantage: any modification to the permutation entries is not thread-safe! Would require permutation copies for nested or concurrent calls with the same permutation.</strong></em></p>
<p>Instead of modifying permutation entries, modifying the array elements with a flag would be more useful. Low-Level languages often have access to reference values (addresses) where an unused bit can be set as a flag and later removed. Non-negative integer values could use the sign as flag as well (in Java). Since the input array needs to be modified anyways with an inplace algorithm, it would not cause additional problems.</p>

CC BY-SA 4.0
2023-01-09T11:55:00.983Z
2023-01-10T20:50:09.233Z
2023-01-10T20:50:09.233Z
ChrisoLosoph
<p>Any permutation of N items can be converted to any other permutation using N-1 or fewer exchanges. Worst case for this method can require O(n^2) calls to the your oracle, F(). Start from the least position. Let x be the position we are currently swapping.</p>

<p>If F(x) >= x then swap positions x and F(x). Else, we must find where the item that was in position F(x) is currently in the list. We can do this with the following iteration. Let y=F(x). Do until y>=x: y=F(y): End Do. Now exchange positions x and y.</p>

CC BY-SA 3.0
2011-05-25T09:25:49.677Z
OP already said he knows how to do it in $O(n^2)$ time.
Jukka Suomela
CC BY-SA 3.0
2011-05-26T02:21:23.743Z
Sorry. I am new to this group. I like this method because of its simplicity. I sometimes find simplicity faster than efficiency. I know another method that requires O(n) steps, but O(nlogn) space.
Russell Easterly
CC BY-SA 3.0
2011-05-26T03:12:04.493Z
Russell, even allocating and zeroing O(n log n) space is already O(n log n), did you mean in the other direction?
jkff
CC BY-SA 3.0
2011-05-26T03:27:44.020Z
You don't really have allocate and zero space. The basic idea is when F(x) > x we need to remember where we put the item at position x. For really large n, I would use a database and just keep a record of where item x gets moved. The record could be deleted when x gets to its final location.
Russell Easterly
CC BY-SA 3.0
2011-05-26T04:02:25.100Z
But why are you then saying that it requires O(n log n) space?
jkff
CC BY-SA 3.0
2011-05-26T05:14:47.287Z
Again I apologise. I am not a computer scientist. I just found the problem interesting. When I said O(n) steps, I meant I only had to loop through F() once. If intitializing an array takes nlogn steps, then my method requires at least that many steps. By nlogn space I mean it requires n numbers of logn size. There could be O(n) items that have been moved and aren't in their final position.
Russell Easterly
CC BY-SA 3.0
2011-05-26T14:38:36.420Z
This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit array. Set all n bits to 0.
Russell Easterly
CC BY-SA 3.0
2011-05-24T20:30:28.153Z
2011-05-25T02:09:37.870Z
2011-05-25T02:09:37.870Z
Russell Easterly
<p>This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit array. Set all n bits of B to 0.</p>

<p>FOR x=1 to n-1: IF B(x)==0 THEN: y=G(x): DO UNTIL x==y: Swap positions x and y: B(y)=1: y=G(y): LOOP: ENDIF: NEXT X</p>

<p>This method keeps swapping the item currently in position x to item's final position. The inner loop ends when the correct item gets swapped into position x. Since each swap moves at least one item to the item's final position, the inner Do loop can't excute more than n-1 times during the run. I think this method is O(n) time and space.</p>

CC BY-SA 3.0
2011-05-26T18:06:46.253Z
Have you looked at the paper? The two algorithms you list here are the two "obvious" ones. The paper has less obvious ones with different time-space tradeoffs, in particular much less space.
Yuval Filmus
CC BY-SA 3.0
2011-05-26T14:58:59.770Z
2011-05-26T14:58:59.770Z
Russell Easterly
<p>To my surprise, I was not able to find papers about this - probably searched the wrong keywords.</p>

<p>So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.</p>

<p>How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?</p>

<p>Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?</p>

<p>I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...</p>

CC BY-SA 3.0
2011-05-24T18:38:05.817Z
An easy observation: If not only the array of the items but also the array containing the function f is writable, then it is easy to perform the task in O(n) time using O(1) integer registers (each of length O(log n) bits) and additional space for one item by just following each cycle.  But this does not work if the function f is given on a read-only storage (or f is given only as an oracle), which I think is an assumption in this question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-05-24T19:06:47.463Z
[Fich et al. 1995](http://dx.doi.org/10.1137/S0097539792238649): $O(n \log n)$ time, $O(\log n)$ space. It also discusses some special cases.
Jukka Suomela
CC BY-SA 3.0
2011-05-24T21:33:25.470Z
Yes, I am assuming we have f as an oracle.
jkff
CC BY-SA 3.0
2012-04-23T16:02:44.387Z
@JukkaSuomela, you should make that into an answer.  Also, considering that $f$ is an arbitrary permutation, a simple entropy argument yields $O( n \log n)$ space and/or time, so I would be surprised if you could do better than $O(n \log n)$ in time _and_ space.
user834
<ds.algorithms><co.combinatorics><permutations>
Complexity of applying a permutation in-place
jkff
# Complexity of applying a permutation in-place

(Asked by: username_0 on 2011-05-24)

To my surprise, I was not able to find papers about this - probably searched the wrong keywords.

So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.

How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?

Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?

I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...

**Tags:** ds.algorithms, co.combinatorics, permutations
> **Comments:**
> **username_1**: An easy observation: If not only the array of the items but also the array containing the function f is writable, then it is easy to perform the task in O(n) time using O(1) integer registers (each of length O(log n) bits) and additional space for one item by just following each cycle.  But this does not work if the function f is given on a read-only storage (or f is given only as an oracle), which I think is an assumption in this question.  
> **username_2**: [Fich et al. 1995](http://dx.doi.org/10.1137/S0097539792238649): $O(n \log n)$ time, $O(\log n)$ space. It also discusses some special cases.  
> **username_0**: Yes, I am assuming we have f as an oracle.  
> **username_3**: @JukkaSuomela, you should make that into an answer.  Also, considering that $f$ is an arbitrary permutation, a simple entropy argument yields $O( n \log n)$ space and/or time, so I would be surprised if you could do better than $O(n \log n)$ in time _and_ space.  

---

## 5 answers

### Answer by username_4 on 2014-01-21. Score: 5

Option 0: [Permuting In Place](https://citeseerx.ist.psu.edu/pdf/6bb4d720088c4e0b2b039e174d34d2e0fd27c466) (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see [Succinct representation of permutations](https://www.imsc.res.in/%7Evraman/pub/icalp_03.pdf).

Option 2: Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat <http://oeis.org/A186202>

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} \* \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 \* \text{distinct}\\_\text{cycle}\\_\text{lengths})$ time, $O((\#\text{cycles}\\_\text{with}\\_\text{same}\\_\text{size}) \* \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log n)$ space.

> **Comments:**
> **username_5**: the compression methods may not save space in general: the worst case space to store a permutation is $n\log n$. 3, 4, and 5 seem in general as bad as either the solution OP already knows, or the solution by Fich, Munro, and Poblete. And that solution was already pointed out by @Jukka  
> **username_4**: #5 uses less space than #0 by a log (n) factor.  

---

### Answer by username_6 on 2013-07-25. Score: 1

If you use the cycle representation of the permutation, you need 1 additional array element to store the item currently being permuted and you can run through the cycles in at worse O(N) operations.

> **Comments:**
> **username_7**: jkff already said he knows the cycle-following algorithm, so he clearly wants the permutation itself to be treated as (close to) a black box. As he points out in the question, converting from a (nearly) black box to cycle representation could take O(n^2) time.  
> **username_4**: Black box p(i) is fine. You just go around the cycle until you get back to i. The problem is one of Kolomogorov complexity to store the list of items that have been updated so you don't cycle them multiple times. Munro has bounds on that. http://www.itu.dk/people/ssrao/icalp03-a.pdf  

---

### Answer by username_8 on 2023-01-09. Score: 0

First off, I came up with the same algorithm as mentioned by Russell Easterly but I have an additional tweak.
This is the initial algorithm:
for each increasing index i from 1 to length of array
   movealong the permutation cycle of the current elementstarting at$f(i)$ and
       stop at the first permutation entry$k = f(j)$where$j \le i < k$
       or else$k = NaN$
   swap array element at i with element at kif k is not NaN
This alone has a worst-case which is only twice as fast as the algorithm in the OP. But the common average case is much faster. For infinitely large N – under consideration of the geometric distribution of randomly generated permutation functions with $p = P(f(j) > i) = 0.5$ for all $j,i$, we would get N times the expectancy value which is $\mathcal{O}(N)$ time complexity with $\mathcal{O}(1)$ space complexity but it might be worse for real data with finite arrays where the parameter of the geometric distribution is a random process. It is certainly a faster and easier algorithm to implement than the one in the original post.
Now we can optimize the worst case by introducing an opposite function which goes into opposite direction, with decreasing index from last to first and searching for a $f(j \ge i) < i$ each time.
Count the number of permutation lookups of both functions without swapping. Then choose the function with less required lookups to do the job with swapping. You can count in parallel or interleaved (assume a fair share of time so that the slower function does not get most of the time) and interrupt the counting of the slower function when it exceeds the returned count of the faster one. This case, we avoid degenerate cases and probably get a solid average case complexity as worst case (I conjecture). If this is true it would only take 3 times the average complexity of the initial algorithm which is better than square complexity in time and is guaranteed to have constant space complexity since no copies are created and swaps are inplace.
Option 2
I found an inplace-algorithm with assumed (measured) worst case $\mathcal{O}(N·log2(N))$. I thought about avoiding unnecessary visits of permutation entries and noticed that the relation between the index and its permutation entry and is already some kind of binary flag property. Python-Code:
def compute_permutation(array, pi):
    for i in range(len(array)):
        if (j := pi[i]) > i:
            array[i], array[j] = array[j], array[i]
    
    for i in range(len(array)-1,0, -1):
        if (j := pi[i]) < i:
            while pi[j] > j or j > i:
                j = pi[j]
            array[i], array[j] = array[j], array[i]

The algorithm yet allows for some further optimizations like avoiding walking through the full cycle for the first permutation entry which points back. I wonder, if walking through the cycles a logarithmic number of times is actually necessary when there are only few array elements left at position < i.
Option 3
For a special case with mutable permutation, if destroying the permutation is not minded, then you can do this (Python):
def compute_permutation(array, pi):
    for i in range(len(array)):
        j = i
        while i != (k := pi[i]):
            array[j], array[k] = array[k], array[j]
            pi[i], pi[k] = pi[k], pi[i]
            j = k

Does not allocate additional memory besides local variables and has $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ space complexity. The trick is to exploit the permutation as buffer which turns it into a linear range of indices at the end. This is probably not worse than the compression options found in the answer of Chad Brewbaker which also destroys the original value of the permutation entries.
Option 4
If there is a way to extract the original index from a given array-element in $\mathcal{O}(1)$ steps and space via a function index_of() then you can do even better without modifying the permutation function but same complexity lower bounds. Just use the comparison of that element index against the permutation entry as a flag:
def compute_permutation(array, pi):
    for i in range(len(array)):
        if array[i].index_of() != pi[i]:
            j = i
            while i != (k := pi[j]):
                array[j], array[k] = array[k], array[j]
                j = k

Option 5
If there is no way to extract the original index of a value in $\mathcal{O}(1)$ time then there is still a way that will always work in practice, even though some could consider it cheating. You can use signed indices and use the sign bit as a flag that is cleared at the end of the algorithm. Set the flag for permutation entries whose corresponding element was already swapped to the correct position. This is always feasible in practice, at least in Java which always reserves a sign bit for integer values even though it is useless for indices.
void compute_permutation(Object[] array, int[] pi)
{
    for(int i=0; i= 0)
        {
            for(int j=i, k; i != (k = pi[j]); j = k)
            {
                Object tmp = array[j];
                array[j] = array[k];
                array[k] = tmp;
                pi[j] = ~pi[j];
            }
        }
    }

    for(int i=0; i
This allows for practical inplace solutions with $\mathcal{O}(N)$ overhead and no additional allocation. Only restriction: requires a writable permutation array.
Big disadvantage: any modification to the permutation entries is not thread-safe! Would require permutation copies for nested or concurrent calls with the same permutation.
Instead of modifying permutation entries, modifying the array elements with a flag would be more useful. Low-Level languages often have access to reference values (addresses) where an unused bit can be set as a flag and later removed. Non-negative integer values could use the sign as flag as well (in Java). Since the input array needs to be modified anyways with an inplace algorithm, it would not cause additional problems.


---

### Answer by username_9 on 2011-05-24. Score: -1

Any permutation of N items can be converted to any other permutation using N-1 or fewer exchanges. Worst case for this method can require O(n^2) calls to the your oracle, F(). Start from the least position. Let x be the position we are currently swapping.

If F(x) >= x then swap positions x and F(x). Else, we must find where the item that was in position F(x) is currently in the list. We can do this with the following iteration. Let y=F(x). Do until y>=x: y=F(y): End Do. Now exchange positions x and y.

> **Comments:**
> **username_2**: OP already said he knows how to do it in $O(n^2)$ time.  
> **username_9**: Sorry. I am new to this group. I like this method because of its simplicity. I sometimes find simplicity faster than efficiency. I know another method that requires O(n) steps, but O(nlogn) space.  
> **username_0**: Russell, even allocating and zeroing O(n log n) space is already O(n log n), did you mean in the other direction?  
> **username_9**: You don't really have allocate and zero space. The basic idea is when F(x) > x we need to remember where we put the item at position x. For really large n, I would use a database and just keep a record of where item x gets moved. The record could be deleted when x gets to its final location.  
> **username_0**: But why are you then saying that it requires O(n log n) space?  
> **username_9**: Again I apologise. I am not a computer scientist. I just found the problem interesting. When I said O(n) steps, I meant I only had to loop through F() once. If intitializing an array takes nlogn steps, then my method requires at least that many steps. By nlogn space I mean it requires n numbers of logn size. There could be O(n) items that have been moved and aren't in their final position.  
> **username_9**: This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit array. Set all n bits to 0.  

---

### Answer by username_9 on 2011-05-26. Score: -2

This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit array. Set all n bits of B to 0.

FOR x=1 to n-1: IF B(x)==0 THEN: y=G(x): DO UNTIL x==y: Swap positions x and y: B(y)=1: y=G(y): LOOP: ENDIF: NEXT X

This method keeps swapping the item currently in position x to item's final position. The inner loop ends when the correct item gets swapped into position x. Since each swap moves at least one item to the item's final position, the inner Do loop can't excute more than n-1 times during the run. I think this method is O(n) time and space.

> **Comments:**
> **username_10**: Have you looked at the paper? The two algorithms you list here are the two "obvious" ones. The paper has less obvious ones with different time-space tradeoffs, in particular much less space.  

---

