java - very very rougly sorting -

suppose have array ( int[] m ).

i need sort it... result must be:

all items in first half must less or equal items in second half.

how it?...

as karl mentioned in comment, task equal partinioning step in quicksort algorithm with exception have find sample median first , use pivot element.

computing median can computed o(n) operations, partinioning step linear (o(n)), overall worst-case performance still better full sorting (o(n log(n)).

the algorithm go (standard methods need implemented):

public int[] roughsort(int[] input) {   int pivot = findmedian(input);   int[] result = partition(input, pivot);   return result; }