How to merge two sorted portions of same array in O(n) time and O(1) space [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicates:

How to sort in-place using the merge sort algorithm?

Regarding in-place merge in an array

Given an array of size N, which is divided into two sets of sorted integers(0 to P and P+1 to N-1). How would you sort this ar开发者_开发技巧ray using constant extra space (O(1)) and in O(n) time. For e.g

A = {1,3,5,7,2,4,6,8}, here N = 8, P = 3 and elements from 0 to 3 are sorted and elements from 4 to 7 are sorted.

Desired O/P: A = {1,2,3,4,5,6,7,8}

---

Your input array doesn't need to be sorted. You simply write out the numbers 0..N-1 (or 1..N your example is a bit confusing). I think you must have mis-stated your problem.

---

If I understand you correctly, you can allocate a new array to hold the result. So what you're doing is merging two sorted lists. A simple two-way merge does that nicely.