c# - Sort integer array in strictly O(n) time -

i asked question in interview .

given sorted integer array containing negative , positive numbers , how resort array based on absolute values of elements ?

this had done strictly in o(n) time.

input

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

output

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

what possible solutions other o(n) time ?

basically, we're going have 2 heads, 1 looking @ end of array, 1 @ beginning.

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

we compare absolute value of 2 entries our heads pointing @ , insert larger our new, sorted array. here 14.

new array: {14}

we move head of whichever item selected closer center. here move our head pointing @ 14 8.

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

we repeat process, inserting larger of 2 absolute values beginning of our new, sorted array. here -9, |-9| > |8|

new array: {-9, 14}

and after move head again:

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

repeat until both heads meet in center

Print F