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 ?

Find the mid point (as in closest to zero) and merge the array from there in both directions- this reduces to merge two sorted subarrays which is guaranteed O(n). — Thomas Jungblut, Mar 21 '15 at 15:23
@mmhasann It's simple, you take the middle of the array (in our case 1), which must be the first number in the new array (because we are guaranteed a sorted array in the input). Then, you merge the two halves (upper and lower): middle = 1 -> first of first half = -3 -> first of second half = 6 -> second of first half = -7 -> second of the second half = 8, ... You get: 1, -3, 6, -7, 8, -9, 14 — barca_d, Mar 21 '15 at 15:28

score 14 · Accepted Answer · answered Mar 21 '15 at 15:40

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

Nice, of course you can just merge from the endings directly- skips finding the pivot. Well done! — Thomas Jungblut, Mar 21 '15 at 15:41

score 2 · Answer 2 · edited May 23 '17 at 12:22

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.

Peter Duniho · Answer 3 · 2015-03-21T15:50:16.177

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++];
    }
}

Sort integer array in strictly O(n) time

3 Answers3