Given:

array of lengthncontaining negative and positive integers in random order.

You have to rearrange the contents of the array so that all negative integers appear at lower array indices ("before") any positive integer. The order of the negative and positive numbers versus others of the same sign is not important ( you don't need to sort them). How can we build this program so that the run time is (n)?