So I have code producing k sorted intervals in an n-sized array. What I'm brainstorming is the possibility of in-place merge of these intervals into a single sorted interval/array. The problem is managing space-complexity.
For simplicity consider the problem of in-place merging just two intervals into a single sorted interval (the length of the array).
For a starters I'm looking for an algorithm that does this merge operation in-place, meaning I do not require an auxiliary n-sized array as is the case with mergesort, as that would be impractical with my data size. Also, I must avoid recursive algorithms.
There is of course the question of efficiency associated with this, in terms of number of comparisons, swaps and locality of reference, but that is something I'm aware of.
Note: I have researched this topic some (and for some time), so be wary of posting links to other questions or trivial solutions(I have considered insertion sort), unless you have sound reason for it.