Merge two sorted parts of an array with constant memory in O(n) time

Question

Hi!

Assume we have an array of length N where the subarrays from 0 to N/2 and N/2 to N elements are sorted. Is it possible to sort the whole array using constant memory in O(N) time?

Example of an array:

10, 20, 30, 40, 1, 2, 35, 60

Answer 1

You want in place merging. See this and this. Also, searching google for "in place merging" will give you a lot of good results. The algorithms aren't easy to implement nor fast in practice, so usually no one bothers with them.