well doing it in O(n) is a research problem...
stackoverflow.com/questions/15400585/in-place-sort-an-array-with-2-sorted-sub-arrays
it's not that easy... for given problem quicksort or heapsort would work
fine...
On May 27, 2013 7:48 PM, bharat b bagana.bharatku...@gmail.com wrote:
@Nishan :
@Nishan :
For the given example, the number of elements which are not in order may be
less ..can u prove this ?
And also, how can u place an incorrect positioned number at correct
position --- takes O(n) for each number
On Sun, May 26, 2013 at 8:55 PM, Ankit Agarwal
@nishant: I think this won't work in all the cases as you said in a
statement: one or two element won't be at correct positions.. there
might be more in other cases unless you prove it somehow. what if
array is too large and there are too many elements not at correct
position after second pass.
An array is given, first and second half are sorted .. Make the array
sorted inplace... Need an algo better than O(n^2)..
If the length of the array is odd.. middle is either in first half or
second half.
Ex:
1. Arr[] = {2,3,6,8,-5,-2,3,8} -- output : Arr[]={-5,-2,2,3,3,6,8,8};
2. Arr[] =
The solution could be given in this way.
1) In one pass get the end index of both array says e1 and e2.
2) now in next pass compare elements at e1 and e2 .
a) if a(e1) a(e2) swap the elements and then decreament e1 and e2 both.
b) if a(e1) a(e2) decreament e2.
c) if a(e1) == a(e2) then
The first pass is not necessary. We can finding the middle element as
follows:
N = even, Range [ 0 - (N/2 - 1) ] [ N/2 - (N - 1) ]
N = odd,
if (A[N/2] A[N/2 -1]) Range [ 0 - N/2 ] [ (N/2 + 1) - (N
- 1) ]
else if ( A[N/2] A[N/2 + 1]) Range [ 0 - (N/2 - 1) ] [
