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.

  • 1
    asked and answered on SO: stackoverflow.com/q/2571049/731620 – ratchet freak Nov 3 '14 at 16:29
  • @ratchetfreak if you'd have actually read the question you'd notice me specifically mention that mergesort is not an option. EDIT: looks like the fault is with me for not reading the posted question, but just the title. I will read into it, thank you. – Nisk Nov 3 '14 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.