Method 1: Square then Sort

This approach squares each element first and subsequently sorts the resulting array.

#include <stdio.h>
#include <stdlib.h>

int compareElements(const void* first, const void* second) {
  int elemA = *((int*)first);
  int elemB = *((int*)second);
  if (elemA < elemB) return -1;
  if (elemA > elemB) return 1;
  return 0;
}

int* squareAndSort(int* inputArray, int arrLength, int* resultLength) {
  // Square every element in place
  for (int idx = 0; idx < arrLength; idx++) {
    inputArray[idx] = inputArray[idx] * inputArray[idx];
  }
  
  // Perform an in-place sort
  qsort(inputArray, arrLength, sizeof(int), compareElements);
  
  // Set the output size
  *resultLength = arrLength;
  
  return inputArray;
}

int main(void) {
  int sample[] = { -7, -3, 2, 4, 9 };
  int length = sizeof(sample) / sizeof(sample[0]);
  int outputSize;
  int* sortedResult = squareAndSort(sample, length, &outputSize);

  printf("Sorted Squares: ");
  for (int i = 0; i < outputSize; i++) {
    printf("%d ", sortedResult[i]);
  }
  printf("\n");
  return 0;
}

The time complexity for this method is O(n + n log n), dominated by the sorting step.

Method 2: Two-Pointer Technique

Given the input array is sorted in non-decreasing order, squaring can place the largest value at either end, not in the midddle. A two-pointer technique efficient constructs the sorted squares from the outside in.

int* computeSortedSquares(int* numbers, int count, int* outputCount) {
    // Allocate memory for the result
    int* resultArray = malloc(sizeof(int) * count);
    *outputCount = count;
    int left = 0;
    int right = count - 1;
    int insertPos = count - 1;

    while (left <= right) {
        int sqLeft = numbers[left] * numbers[left];
        int sqRight = numbers[right] * numbers[right];
        
        // Place the larger square at the current insertion position
        if (sqLeft > sqRight) {
            resultArray[insertPos] = sqLeft;
            left++;
        } else {
            resultArray[insertPos] = sqRight;
            right--;
        }
        insertPos--;
    }
    return resultArray;
}

This approach runs in O(n) time with O(n) auxiliary space.

Method 3: Merge Strategy Using Partition

First, locate the index separating non-negative and negative numbers. The squares of the neagtive portion are in decreasing order, while the squares of the non-negative portion are in increasing order. Merge these two sorted sequences.

int* mergeSortedSquares(int* numbers, int count, int* outputCount) {
  // Find the last index of a negative number
  int splitIdx = -1;
  for (int i = 0; i < count; ++i) {
    if (numbers[i] < 0) {
      splitIdx = i;
    } else {
      break;
    }
  }

  int* finalArray = malloc(sizeof(int) * count);
  *outputCount = 0;
  int neg = splitIdx;          // Pointer for negative segment (moves left)
  int nonNeg = splitIdx + 1;   // Pointer for non-negative segment (moves right)

  while (neg >= 0 || nonNeg < count) {
    if (neg < 0) {
      // Exhausted negative segment
      finalArray[(*outputCount)++] = numbers[nonNeg] * numbers[nonNeg];
      ++nonNeg;
    } else if (nonNeg >= count) {
      // Exhausted non-negative segment
      finalArray[(*outputCount)++] = numbers[neg] * numbers[neg];
      --neg;
    } else {
      // Compare squares from both segments
      int sqNeg = numbers[neg] * numbers[neg];
      int sqNonNeg = numbers[nonNeg] * numbers[nonNeg];
      if (sqNeg < sqNonNeg) {
        finalArray[(*outputCount)++] = sqNeg;
        --neg;
      } else {
        finalArray[(*outputCount)++] = sqNonNeg;
        ++nonNeg;
      }
    }
  }
  return finalArray;
}