# Questions tagged [in-place]

When something happens with only a constant amount of extra space, it is said to happen in-place.

15 questions
Filter by
Sorted by
Tagged with
278 views

### Is radix sort in-place or out-place?

Generally, we can implement algorithms in-place and out-of-place. However, I can't say for certain that radix sort can be implemented in both ways.
1 vote
111 views

### Index variable takes up log(n) space?

In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits." How does an array index ...
45 views

### In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
122 views

### LinkedList: Remove the kth node form the end

Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
1 vote
241 views

### In-place matrix transposition using rotations

Some time ago I invented an algorithm for in-place matrix transposition using rotations. A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage ... 38 views

### In-place patching of diff between two sets?

For two ordered sets of keys Paul Heckel's diffing algorithm generates the necessary actions to transform, or patch, one set to the other. I am asking how you'd do the patching without keeping a copy ...
544 views

### Interleaving first and second half of an array of even length in place

If A is an array with the following elements: $$a_1,a_2,...,a_n,b_1,b_2,...,b_n$$ How to shuffle A to form: $$a_1,b_1,a_2,b_2,...,a_n,b_n$$ with minimal swaps and using no additional space? I ...
710 views

### Sorting in place & stable in linear time

Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics- The algorithm runs in $O(n)$ time. The algorithm is stable. The algorithm sorts ...
210 views

### Inplace sorting of variable length records

Is there an in-place algorithm for sorting variable length records? For example a vector of arbitrary length strings. Most provided in-place algorithms assume that you can switch two elements ...
5k views

### What is the most efficient constant-space sorting algorithm?

I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions: SWAP: swap the next index with the current one; ...
8k views

### Merge two sorted arrays without using additional memory

We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the ...
280 views

### Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
440 views

### Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
### Worst case $O(n \ln n)$ in place stable sort?
I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...
You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like ...