Given an array of integers, reorder so that all the negative integers appear first, then the zeroes, and finally the positive integers. If two integers have the same sign, their order should not be changed. Use O(1) extra storage. Can this be done in O(n)? Or does it have to be O(nlogn) for lower bound?