How to implement what I call a "wraparound sort" around an arbitrary value in C++?

Question

Given a vector of ints, I would like to implement what I am calling in my mind a "wraparound sort." Basically, given an arbitrary value, all of the values greater than or equal to that value are listed first in ascending order, and than all values less than the arbitrary value, again in ascending order. For a value of 12, a wraparound sorted array would look like:

[13, 15, 18, 29, 32, 1, 3, 4, 8, 9, 11]

What would be a way to implement such a sort? I am fine assuming as a starting point a vector that is already sorted in ascending order without the wraparound characteristic, since it's easy enough to get to that state, if such an assumption is useful.

Answer 1

You can do this combining std::partition and std::sort. std::partition will split the vector around the partition point and then you can use std::sort to sort both halves. That would look like

int main()
{
    std::vector vec = {1,3,4,8,9,11,13,15,18,29,32};
    // all elements >= 12 come first, return value is end iterator of that set
    auto front_end = std::partition(vec.begin(), vec.end(), [](auto elm){return elm >= 12;});
    // sort first half
    std::sort(vec.begin(), front_end);
    // sort second half
    std::sort(front_end, vec.end());
    for (auto e : vec)
        std::cout << e << " ";
}

which outputs

13 15 18 29 32 1 3 4 8 9 11 

---

From PaulMcKenzie's comment you can reduce the code size a little bit by using std::stable_partition on a sorted vector. That would look like

int main()
{
    std::vector vec = {1,3,4,8,9,11,13,15,18,29,32};
    // sort the vector
    std::sort(vec.begin(), vec.end());
    // all elements >= 12 come first in the order they had in the sorted vector
    std::stable_partition(vec.begin(), vec.end(), [](auto elm){return elm >= 12;});
    for (auto e : vec)
        std::cout << e << " ";
}

It should be noted that std::stable_partition does try to do an allocation to be as efficient as std::partition and if it can't do that then it falls back to a less efficient O(NlogN) algorithm.