Объединяет две отсортированные внутренние последовательности из той же последовательности в единую, упорядоченную последовательность. Внутренние последовательности от beg до mid и от mid до end объединяются и записываются назад в первоначальную последовательность. Первая версия использует для сравнения элементов оператор <, а вторая версия использует заданную операцию сравнения. Возвращают void.
А.2.5. Алгоритмы сортировки и разделения
Алгоритмы сортировка и разделения предоставляют различные стратегии упорядочивания элементов последовательности.
Каждый алгоритм сортировки и разделения поддерживает стабильные и нестабильные версии (см. раздел 10.3.1). Стабильный алгоритм обеспечивает относительный порядок равных элементов. Стабильные алгоритмы выполняют больше работы, а следовательно, могут выполняться медленней и использовать больше памяти, чем нестабильные аналоги.
Алгоритмы разделения делят элементы исходного диапазона на две группы. Первая группа состоит из элементов удовлетворяющих определенному предикату, а вторая — нет. Например, элементы последовательности можно разделить на основании четности их значений или на основании того, начинается ли слово с заглавной буквы, и так далее. Этим алгоритмам требуются двунаправленные итераторы.
is_partitioned(beg, end, unaryPred)
Возвращает значение true, если все элементы, удовлетворяющие предикату unaryPred, предшествуют тем, для которых предикат unaryPred возвращает значение false. Если последовательность пуста, также возвращается значение true.
partition_copy(beg, end, dest1, dest2, unaryPred)
Копирует в dest1 элементы, для которых истин предикат unaryPred, а остальные копирует в dest2. Возвращает пару (см. раздел 11.2.3) итераторов. Член first пары обозначает конец скопированных в dest1 элементов, а член second обозначает конец элементов, скопированных в dest2. Исходная последовательность не может налагаться ни на одну из результирующих последовательностей.
partition_point(beg, end, unaryPred)
Для разделения исходной последовательности используется предикат unaryPred. Возвращает итератор на элемент за последним, удовлетворяющим предикату unaryPred. Если возвращен итератор не end, то предикат unaryPred должен возвращать значение false для возвращенного итератора и для всех элементов, следующих за ним.
stable_partition(beg, end, unaryPred)
partition(beg, end, unaryPred)
Для разделения исходной последовательности используется предикат unaryPred. Элементы, для которых истин предикат unaryPred, помещаются в начало последовательности, а остальные в конец. Возвращает итератор на элемент за последним, удовлетворяющим предикату unaryPred, или итератор beg, если таких элементов нет.
Этим алгоритмам требуются итераторы прямого доступа. Каждый из алгоритмов сортировки предоставляется в двух перегруженных версиях. В одной из них для сравнения элементов используется оператор < типа элемента, а во второй предусмотрен дополнительный параметр для функции сравнения (см. раздел 11.2.2). Алгоритм partial_sort_copy() возвращает итератор получателя, а остальные возвращают void.
Алгоритмы partial_sort() и nth_element() выполняют частичную сортировку последовательности. Их используют в случае, когда в результате сортировки всей последовательности могут возникнуть проблемы. Поскольку эти операции являются менее трудоемкими, они выполняются быстрее, чем сортировка всего исходного диапазона.
sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)
Сортирует весь диапазон.
is_sorted(beg, end)
is_sorted(beg, end, comp)
is_sorted_until(beg, end)
is_sorted_until(beg, end, comp)
Алгоритм is sorted() возвращает логическое значение, указывающее, сортируется ли вся исходная последовательность. Алгоритм is_sorted_until() находит самую длинную изначально отсортированную часть в исходной последовательности и возвращает итератор на позицию сразу после ее конца.
partial_sort(beg, mid, end)