Efficiently squaring each element in a sorted array, keeping it sorted

The other day I was asked the following question during an interview:


Given a sorted array, how would you square each element of this array, while keeping it sorted?

I froze up and wrote a horribly inefficient solution I've included below. Basically, I iterate through the original array, squaring each element, and then sort that array via bubble sort. (I know, I could do better, but it's what came to mind at first).

Is there a way to do this more efficiently, perhaps an \$\mathcal{O}(N)\$ solution?

void bubbleSort(int *arr, int length);

int main(int argc, const char * argv[]) {

    int arr[] = {-3,-2,0,4,5,8};

    for(int i = 0; i < 6; i++) {
        arr[i] *= arr[i];
    }

    bubbleSort(arr, 6);

    for(int j = 0; j < 6; j++)
        cout << arr[j] << endl;
}

void bubbleSort(int *arr, int length) {
    int temp;

    for(int i = 0; i < length; i++) {
        for(int j = 0; j < length; j++) {
            if(arr[j] < arr[j+1]) {
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

Elements can be negative or positive.

It can be done in O(n) time. Split your array into two logical parts. Positive and negative. Then apply square to each element in both arrays. Then merge the arrays( merging can be done in O(n) ), but merge the array with previously negative integers in reverse order, since its values will be reversed.

StackExchange Code Review Q#75819, answer score: 69