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

Question

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 array 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}

Answer 1

http://en.wikipedia.org/wiki/Radix_sort

Linear sorting time, no extra space required.

Answer 2

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.

Answer 3

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.