Search code examples
algorithmpositionsorting

sort an array by relative position

Give a array which has negative and positive integers,implement a algorithm that costs O(n) time and O(1) spaces to make all negative integers in front of all positive integers, and keep the relative position. for example:{1,7,-5,9,-12,15} -----> {-5,-12,1,7,9,15}

do you have any ideas?

Solution

  • You are asking for a stable in-place partition function.

    The paper Stable Minimum Space Partitioning in Linear Time (1992) claims to have such an algorithm, but some other SO questions have raised doubts about its feasibility.