Introduction

In-place reordering means changing the order of an array without allocating another full array for the result. The hard part is not swapping values, but doing it safely when the target order is described by a permutation and every move risks overwriting data you still need.

Clarify The Problem First

There are several kinds of "reordering":

• reversing an array
• rotating left or right
• sorting
• applying an arbitrary permutation

The first three have specialized algorithms. The most general case is permutation-based reordering, where you are given a mapping that says where each element should go.

For example:

• array: ['A', 'B', 'C', 'D']
• target positions: [2, 0, 3, 1]

This means the element at index 0 should move to index 2, index 1 should move to 0, and so on.

The Core Idea: Follow Cycles

A permutation can be decomposed into cycles. If you process one cycle at a time, you can rotate the values within that cycle using only a temporary variable.

Suppose the permutation contains a cycle:

0 -> 2 -> 3 -> 1 -> 0

You can move the values around that loop without allocating another whole array.

A Python Example

Here is an in-place algorithm that reorders arr according to perm, where perm[i] is the destination index for the value currently at i.

1def reorder_in_place(arr, perm):
2    n = len(arr)
3    if len(perm) != n:
4        raise ValueError("arr and perm must have the same length")
5
6    for start in range(n):
7        current = start
8
9        while perm[current] != current:
10            next_index = perm[current]
11            arr[current], arr[next_index] = arr[next_index], arr[current]
12            perm[current], perm[next_index] = perm[next_index], perm[current]
13
14    return arr
15
16values = ["A", "B", "C", "D"]
17perm = [2, 0, 3, 1]
18
19print(reorder_in_place(values, perm))

Output:

['B', 'D', 'A', 'C']

This works by fixing positions one by one. Each swap moves at least one element into its final position, and the permutation array is updated alongside the data.

Why The Permutation Array Gets Modified

The implementation above mutates perm. That is deliberate. Once a position is fixed, the code marks it by making perm[i] == i.

If you are not allowed to modify perm, you need either:

• a visited array, which costs extra space
• arithmetic encoding tricks, which are less readable and depend on value constraints

So in interview-style problems, always ask whether mutating the permutation is allowed. It changes the solution space.

Specialized In-Place Reorders

Not every reorder needs full permutation logic.

To reverse an array:

1def reverse_in_place(arr):
2    left, right = 0, len(arr) - 1
3    while left < right:
4        arr[left], arr[right] = arr[right], arr[left]
5        left += 1
6        right -= 1

To rotate an array right by k, the classic in-place technique is three reversals:

def rotate_right(arr, k):
    k %= len(arr)
    arr[:] = arr[-k:] + arr[:-k]

That last Python version is not strictly in-place in the algorithmic sense because slicing allocates extra storage. In low-level languages, the three-reversal method is the true constant-space approach.

Complexity

For permutation-based reordering:

• time complexity is linear, because each element is moved a bounded number of times
• extra space is constant if you are allowed to modify the permutation array

That is why cycle-based algorithms are the standard answer.

Common Pitfalls

• Forgetting to define whether perm[i] means source index or destination index.
• Overwriting values before they have been moved to their target location.
• Assuming the algorithm is in-place even though it quietly uses slicing or a second array.
• Failing to validate that perm is a valid permutation of 0 through n - 1.
• Ignoring whether mutating the permutation array is allowed by the problem.

Summary

• In-place reordering is easiest to reason about as permutation cycles.
• If perm may be mutated, you can often reorder in linear time with constant extra space.
• Specialized reorders such as reverse and rotation have simpler dedicated algorithms.
• Always clarify the meaning of the permutation mapping before coding.
• Beware of Python slices, which are convenient but not truly constant-space.