Sort integer array in strictly O(n) time

Question

I was asked this question in interview recently .

Given a sorted integer array containing negative and positive numbers , how to resort the array based on absolute values of elements ?

This had to be done strictly in O(n) time.

Input

{-9,-7,-3,1,6,8,14}

Output

{1,-3,6,-7,8,-9,14}

What are the possible solutions other than O(n) time ?

Answer 1

Basically, we're going to have 2 heads, one looking at the end of the array, one at the beginning.

  v                   v
{-9, -7, -3, 1, 6, 8, 14}

We compare the absolute value of the 2 entries our heads are pointing at and insert the larger into our new, sorted array. So here it would be 14.

New array: {14}

We then move the head of whichever item we selected closer to the center. So here we move our head pointing at 14 to 8.

  v                v   
{-9, -7, -3, 1, 6, 8, 14}

We then repeat the process, inserting the larger of the 2 absolute values into the beginning of our new, sorted array. Here that would be -9, as |-9| > |8|

New array: {-9, 14}

And after we move the head again:

      v            v        
{-9, -7, -3, 1, 6, 8, 14}

Repeat until both heads meet in the center

Answer 2

Let's take your example:

{-9,-7,-3,1,6,8,14}

You could rewrite this into two parts:

{-9,-7,-3} and {1,6,8,14}

Two obvious observations:

• The left part is sorted descending
• The right part is sorted ascending

Now you basically just merge these two sorted subarrays, which is possibly in linear time. Have a look for the algorithm here How to merge two sorted arrays into a sorted array?.

Since you don't have these arrays split up, you find the point in the array which flips negative to positive. From that split-point, you can go index by index until the boundaries of the array and reconstruct a sorted array again.

Answer 3

As mentioned in the comments, you are basically looking at a merge sort. The original data is already sorted, so all you have to do is retrieve the values in order from each of the negative and positive sets of numbers, merging them according to their absolute values.

The code would look something like this:

int[] input = { -9, -7, -3, 1, 6, 8, 14 };
int[] output = new int[input.Length];
int negativeIndex, positiveIndex = 0, outputIndex = 0;

while (input[positiveIndex] < 0)
{
    positiveIndex++;
}

negativeIndex = positiveIndex - 1;

while (outputIndex < output.Length)
{
    if (negativeIndex < 0)
    {
        output[outputIndex++] = input[positiveIndex++];
    }
    else if (positiveIndex >= input.Length)
    {
        output[outputIndex++] = input[negativeIndex--];
    }
    else
    {
        output[outputIndex++] = -input[negativeIndex] < input[positiveIndex] ?
          input[negativeIndex--] : input[positiveIndex++];
    }
}

The above is IMHO somewhat easier to grasp, but as another answer points out, you can do it without even scanning to the 0-point of the data, by sorting from the other end. The code for that would look something like this:

int[] output = new int[input.Length];
int negativeIndex =  0, positiveIndex = input.Length -1, outputIndex = input.Length - 1;

while (outputIndex >= 0)
{
    if (input[negativeIndex] >= 0)
    {
        output[outputIndex--] = input[positiveIndex--];
    }
    else if (input[positiveIndex] < 0)
    {
        output[outputIndex--] = input[negativeIndex++];
    }
    else
    {
        output[outputIndex--] = -input[negativeIndex] < input[positiveIndex] ?
            input[positiveIndex--] : input[negativeIndex++];
    }
}