How can I re-sort a sorted array by absolute values, in linear time?

Question

You are given a sorted array containing both negative and positive values. Resort the array taking absolute value of negative numbers. Your complexity should be O(n)

Sample Input

[-8, -5, -3, -1, 3, 6, 9]

Expected Output

[ -1, -3, 3, -5, 6, -8, 9 ]

I have done this till now, but output is not correct.

function sortMe(input) {
   var newArr = [];
   for (var i = 0; i < input.length; i++) {
     var value = Math.abs(input[i]);
     newArr.push(value);
   }
   var c = newArr.sort()
}

and it is giving output

[ 1, 3, 3, 5, 6, 8, 9 ]

Answer 1

1. Split the array in to two halves, one with negative numbers and the other with positive numbers.

2. Reverse the negative numbers array.

3. Then, run merging algorithm with the absolute value of both the arrays.

Overall runtime complexity is still O(n).

---

function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

console.log(sortMe([-8, -5, -3, -1, 3, 6, 9]));
// [ -1, -3, 3, -5, 6, -8, 9 ]

function sortMe(sortedArray) {

  var idx = -1, negs, pos, result = [], nIdx = 0, pIdx = 0;

  if (sortedArray.length === 0)
    return result;

  // Find the index where positive elements begin
  while (idx < sortedArray.length && sortedArray[++idx] < 0);

  // Get elements till the index and reverse the array
  negs = sortedArray.slice(0, idx).reverse();

  // Get elements from the index till the end
  pos = sortedArray.slice(idx);

  // Merging algorithm implementation which merges `negs` and `pos`
  while (nIdx < negs.length || pIdx < pos.length)
  {
    if (nIdx < negs.length && pIdx < pos.length)
    {
      if (Math.abs(negs[nIdx]) <= pos[pIdx])
        result.push(negs[nIdx++]);
      else
        result.push(pos[pIdx++]);
    }
    else if (nIdx < negs.length)
      result.push(negs[nIdx++]);
    else
      result.push(pos[pIdx++]);
  }

  return result;
}

function getElement(id) {
  return document.getElementById(id);
}

function sorter() {
  var data = getElement("numbers").value.split(" ").map(Number);
  getElement("result").innerHTML = "[" + sortMe(data).join(", ") + "]";
}

<input id="numbers" value="-8 -5 -3 -1 3 6 9" />
<input type="button" onclick="sorter()" value="Click here to Sort" />
<pre id="result" />