I have an excercise in which I have to improve an algorithem. This algorithem takes an array and puts the evens in the left side (SORTED) and the odds in the right side (NOT-SORTED).
The algorithem is inefficient so I have to improve it.

Here is the original code of the excercise, the one I have to "improve":

```
public void what (int [] arr) {
    int temp;
    for (int i=0; i<arr.length; i++)
        if (arr[i]%2 == 0) {
            temp = arr[i];
            for (int j=i; j>0; j--)
                arr[j] = arr[j-1];
            arr[0] = temp;
    }
}

```

I wanted to implement quick sort algorithem on this excercise, but the problem is I don't know how the use the pivot: usually, the pivot is the median, the number half of the array is smaller and the other half is bigger.

The problem here is that the left part has to be evens and the right part, odds. 

I have to implement this "sorting" in an efficiency less than O(n^2).

Any ideas?

Thank you!