CareerCup

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.
Thus, for odd sized array the middle element would be the median.
For lack of editing capability, posting as comment.

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)