# Sort, Binary Search, Merge Algorithms

#### Sort And Partial Sort

You can sort a range with `std::sort` or `std::stable_sort` or sort until a position with `std::partial_sort`. In addition `std::partial_sort_copy` copies the partially sorted range. With `std::nth_element` you can assign an element the sorted position in the range. You can check with `std::is_sorted` if a range is sorted. If you want to know until which position a range is sorted, use `std::is_sorted_until`.

``````std::string str{"RUdAjdDkaACsdfjwldXmnEiVSEZTiepfgOIkue"};
std::cout << std::is_sorted(str.begin(), str.end());        // false

std::partial_sort(str.begin(), str.begin()+30, str.end());

auto sortUntil= std::is_sorted_until(str.begin(), str.end());
std::cout << *sortUntil;                                   // s
for (auto charIt= str.begin(); charIt != sortUntil; ++charIt)

std::vector<int> vec{1, 0, 4, 3, 5};
auto vecIt= vec.begin();
while(vecIt != vec.end()){
std::nth_element(vec.begin(), vecIt++, vec.end());
std::cout << std::distance(vec.begin(), vecIt) << "-th ";
for (auto v: vec) std::cout << v << "/";
}
// 1-th 01435/2-th 01435/3-th 10345/4-th 30145/5-th 10345``````
``````struct A{
int v;
bool operator<(const A& other){
return this->v<other.v;
}
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc,argv);
QList<A> list{{8},{2},{3},{6},{5}};
sort(list.begin(),list.end());
for(const A& a:list){
qDebug()<<a.v;
}//2 3 5 6 8
return a.exec();
}``````

# Binary Search

The binary search algorithms use the fact that the ranges are already sorted. To search for an element, use `std::binary_search`. With `std::lower_bound` you get an iterator for the first element, being no smaller than the given value. With `std::upper_bound` you get an iterator back for the first element, which is bigger than the given value. `std:::equal_range` combines both algorithms.

binary_search : Searches the element `val` in the range
lower_bound : Returns the position of the first element of the range, being not smaller than `val`
upper_bound : Returns the position of the first element of the range, being bigger than `val`
`equal_range`  : Returns the pair `std::lower_bound` and `std::upper_bound` for the element `val`

``````bool isLessAbs(int a, int b){
return abs(a) < abs(b);
}
vector<int> vec{-3, 0, -3, 2, -3, 5, -3, 7, -0, 6, -3, 5,
-6, 8, 9, 0, 8, 7, -7, 8, 9, -6, 3, -3, 2};

sort(vec.begin(), vec.end(), isLessAbs);
for (auto v: vec) cout << v << " ";
// 0 0 0 2 2 -3 -3 -3 -3 -3 3 -3 5 5 -6 -6 6 7 -7 7 8 8 8 9 9
cout << binary_search(vec.begin(), vec.end(), -5, isLessAbs); // true
cout << binary_search(vec.begin(), vec.end(), 5, isLessAbs);  // true

auto pair= equal_range(vec.begin(), vec.end(), 3, isLessAbs);
cout << distance(vec.begin(), pair.first);                    // 5
cout << distance(vec.begin(), pair.second)-1;                 // 11

for (auto threeIt= pair.first;threeIt != pair.second; ++threeIt)
cout << *threeIt << " ";              // -3 -3 -3 -3 -3 3 -3``````

#### Merge Operation

Merge operations empower you to merge sorted ranges in a new sorted range. The algorithm requires that the ranges and the algorithm use the same sorting criterion. If not, the program is undefined. Per default the predefined sorting criterion `std::less` is used. If you use your sorting criterion, it has to obey the strict weak ordering. If not, the program is undefined.

You can merge two sorted ranges with `std::inplace_merge` and `std::merge`. You can check with `std::includes` if one sorted range is in another sorted range. You can merge with `std::set_difference``std::set_intersection``std::set_symmetric_difference` and `std::set_union` two sorted ranges in a new sorted range.

`inplace_merge` : Merges in place two sorted sub ranges `[first, mid)` and `[mid, last)`
merge : Merges two sorted ranges and copies the result to `result`
`includes:` Checks if all elements of the second range are in the first range
set_difference : Copies these elements of the first range to `result`, being not in the second range
set_intersection : Determines the intersection of the first with the second range and copies the result to `result`
`set_symmetric_difference : ` Determines the symmetric difference of the first with the second range and copies the result to `result`
`set_union` : Determines the union of the first with the second range and copies the result to `result`

``````std::vector<int> vec1{1, 1, 4, 3, 5, 8, 6, 7, 9, 2};
std::vector<int> vec2{1, 2, 3};

std::sort(vec1.begin(), vec1.end());
std::vector<int> vec(vec1);

vec1.reserve(vec1.size() + vec2.size());
vec1.insert(vec1.end(), vec2.begin(), vec2.end());
for (auto v: vec1) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 1 2 3

std::inplace_merge(vec1.begin(), vec1.end()-vec2.size(), vec1.end());
for (auto v: vec1) std::cout << v << " ";       //  1 1 1 2 2 3 3 4 5 6 7 8 9

vec2.push_back(10);
for (auto v: vec) std::cout << v << " ";        // 1 1 2 3 4 5 6 7 8 9
for (auto v: vec2) std::cout << v << " ";       // 1 2 3 10

std::vector<int> res;
std::set_symmetric_difference(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 4 5 6 7 8 9 10

res= {};
std::set_union(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 10``````