Move all negative numbers to beginning and positive to end with constant extra space

An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers.

Examples :

Input: -12, 11, -13, -5, 6, -7, 5, -3, -6
Output: -12 -13 -5 -7 -3 -6 11 6 5

Naive approach: The idea is to sort the array of elements, this will make sure that all the negative elements will come before all the positive elements.
Below is the implementation of the above approach:

// Java program to move all negative numbers to the

// beginning and all positive numbers to the end with

// constant extra space

import java.util.*;

public class Gfg {

public static void move(int[] arr)

{

Arrays.sort(arr);

}

// Driver code

public static void main(String[] args)

{

int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 };

move(arr);

for (int e : arr)

System.out.print(e + " ");

}

}

Output

-7 -3 -1 2 4 5 6 8 9

Time Complexity: O(n*log(n)), Where n is the length of the given array.
Auxiliary Space: O(n)