Sort array after converting elements to their squares

Given an array of both positive and negative integers ‘$a[]’. The challenge is to sort the square of the numbers of the array.

Examples:

Input : $a = [-9, -4, 1, 2, 9];
Output : $b = [1, 4, 16, 81, 81];

Input : $a = [-5, -4, -2, 0, 7];
Output : $b = [0, 4, 16, 25, 49];

Simple solution is to first convert each array element to its square and then apply any sorting algorithm (i.e. O(nlogn)).

<?php
// Enter your code here, enjoy!
function sortNegativePositive($a, $n) {
$b = [];
for($i = 0; $i < $n; $i++) {
$a[$i] = $a[$i] * $a[$i];
}

sort($a);
return $a;
}

// Execution will start from here.
$a = [-9, -4, 1, 2, 9];
$n = count($a);

print_r($a); // before sort

$a = sortNegativePositive($a, $n);

print_r($a); // after sort;

And the output is looks like

Array
(
 [0] => -9
 [1] => -4
 [2] => 1
 [3] => 2
 [4] => 9
)
Array
(
 [0] => 1
 [1] => 4
 [2] => 16
 [3] => 81
 [4] => 81
)

Time complexity is : O(n log n) as we use some sorting function (sorting algorithm) to sort it.

The effective and complex solution to sort it is

1. Divide array into Negative and Positive parts, (i.e. 2 parts).
2. Merge both sorted array into single sorted array.