## Interview Question

**Country:**United States

I cannot think of an in-place algorithm right now. but what we can do is:

1. Find the median in O(n) time using quickselect.

2. Using two pointers (one for the elements smaller than the median and one for the larger) copy the elements over to a buffer array preserving the relative order. Smaller elements will be placed in the buffer starting from index = 0 and larger elements will be placed in the array starting from n/2

We also need to handle both of the cases where the original array has even/odd number of elements.

package carrercup;

import java.util.*;

public class array1 {

public static void main(String[] args)

{

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int temp,temp1;

int[] arr=new int[n];

for(int i=0;i<n;i++)

{

arr[i]=sc.nextInt();

}

int[] newarr=new int[n];

for(int r=0;r<n;r++)

{

newarr[r]=arr[r];

}

for(int j=0;j<n;j++)

{

for(int k=j;k<n;k++)

{

if(newarr[k]<newarr[j])

{

temp=newarr[k];

newarr[k]=newarr[j];

newarr[j]=temp;

}

}

}

temp1=newarr[n/2-1];

int count=0;

for(int t=0;t<n;t++)

{

if(arr[t]<=temp1)

{

temp=arr[t];

for(int u=t;u>count;u--)

{

arr[u]=arr[u-1];

}

System.out.println(temp1);

arr[count]=temp;

count++;

}

}

for(int o=0;o<n;o++)

{

System.out.print(arr[o]);

}

}

}

```
void PartitionArray(int* array, int cnt)
{
int* pTmp = new int[cnt];
std::copy(array, array + cnt, pTmp);
std::nth_element(pTmp, pTmp + (cnt-1)/2, pTmp + cnt);
int median = pTmp[(cnt-1)/2];
for (int lIdx = 0, hIdx = (cnt + 1)/2, i = 0; i < cnt; i++)
pTmp[(array[i] <= median) ? lIdx++ : hIdx++] = array[i];
std::copy(pTmp, pTmp + cnt, array);
delete[] pTmp;
}
```

Edited to remove extraneous copy

```
void PartitionArray(int* array, int cnt)
{
int* pTmp = new int[cnt];
std::copy(array, array + cnt, pTmp);
std::nth_element(array, array + (cnt-1)/2, array + cnt);
int median = array[(cnt-1)/2];
for (int lIdx = 0, hIdx = (cnt + 1)/2, i = 0; i < cnt; i++)
array[(pTmp[i] <= median) ? lIdx++ : hIdx++] = pTmp[i];
delete[] pTmp;
}
```

```
// ZoomBA
def left_right( a ){
len = #|a|
odd = !(2 /? len)
left_heap = fold( a , heap( len/2 + 1 ) ) -> { $.partial += $.item }
#(l,r) = fold( a, [list(),list()] ) -> {
if ( $.item < left_heap.max ){ $.partial.0 += $.item }
if ( $.item > left_heap.max ){ $.partial.1 += $.item }
if ( !odd && $.item == left_heap.max ) { $.partial.1 += $.item }
$.partial
}
println ( l + (odd ? left_heap.max : []) + r )
}
a = [ 6, 4, 5, 0, 2, 1, 11 , -1 ]
left_right(a)
a = [ 6, 4, 5, 0, 2, 1, 11 , -1, 9 ]
left_right(a)
```

As you can see, the *left* half has all the small elements while the *right* half has all the large elements. Thus, the problem is partition the array into two halves of equal sizes, left contains all the small elements ( w/o violating the order ) and right has the large ones.

- NoOne October 12, 2016Thus, for odd sized array the middle element would be the median.

For lack of editing capability, posting as comment.